湖北襄阳网站建设,网页版传奇如何作弊?,电子商务网站建设技术有哪些方面,线上招生引流推广方法文章目录1. 题目2. 解题2.1 动态规划超时2.2 二分查找2.3 归并排序1. 题目
给定一个整数数组 nums#xff0c;返回区间和在 [lower, upper] 之间的个数#xff0c;包含 lower 和 upper。
区间和 S(i, j) 表示在 nums 中#xff0c;位置从 i 到 j 的元素之和#xff0c;包…
文章目录1. 题目2. 解题2.1 动态规划超时2.2 二分查找2.3 归并排序1. 题目
给定一个整数数组 nums返回区间和在 [lower, upper] 之间的个数包含 lower 和 upper。
区间和 S(i, j) 表示在 nums 中位置从 i 到 j 的元素之和包含 i 和 j (i ≤ j)。
说明: 最直观的算法复杂度是 O(n2) 请在此基础上优化你的算法。
示例:
输入: nums [-2,5,-1], lower -2, upper 2,
输出: 3
解释: 3个区间分别是: [0,0], [2,2], [0,2]它们表示的和分别为: -2, -1, 2。来源力扣LeetCode 链接https://leetcode-cn.com/problems/count-of-range-sum 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
2.1 动态规划超时
区间动态规划超时例子复杂度太高 O(n2)O(n^2)O(n2)整型溢出例子[2147483647,-2147483648,-1,0] -1 0
class Solution {
public:int countRangeSum(vectorint nums, int lower, int upper) {if(nums.size() 0)return 0;int i, j, len, n nums.size(), count0;vectorvectorlong dp(n,vectorlong(n,0));//区间[i,j]的和for(i 0; i n; i){dp[i][i] nums[i];if(lowerdp[i][i] dp[i][i]upper)count;}for(len 1; len n; len){for(i 0; i n-len; i){dp[i][ilen] dp[i][ilen-1] dp[ilen][ilen];if(lowerdp[i][ilen] dp[i][ilen]upper)count;}}return count;}
};2.2 二分查找
参考大佬的解法前缀和 sum L≤sum[j]−sum[i]≤U⇒sum[j]−U≤sum[i]≤sum[j]−LL \le sum[j]-sum[i] \le U \Rightarrow sum[j]-U\le sum[i] \le sum[j]-LL≤sum[j]−sum[i]≤U⇒sum[j]−U≤sum[i]≤sum[j]−Lj 0 时, 上式 sum[i] 0sum[i] 可以看做前面的和 sum[j] 当前的和以每个 j 点作为结束的区间前面哪些 i 到 j 的和在范围内将前次的前缀和插入multiset有序可以二分查找查找set中前缀值在 当前 前缀和 sum[j]sum[j]sum[j] 上下范围内[sum[j]−U,sum[j]−L][sum[j]-U, sum[j]-L][sum[j]−U,sum[j]−L]的个数
class Solution {
public:int countRangeSum(vectorint nums, int lower, int upper) {if(nums.size() 0)return 0;multisetlong s;s.insert(0);int count 0;long sum 0;for(int i 0; i nums.size(); i){sum nums[i];count distance(s.lower_bound(sum-upper), s.upper_bound(sum-lower));s.insert(sum);}return count;}
};但是上面解法中distance在set中不可随机访问是 O(n)时间复杂度的所以用数组进行二分查找两个端点然后做差会更快些。 80 ms 14.4 MB
2.3 归并排序
其实归并排序求逆序度是本题的一个特例对前缀和进行归并排序注意头部要加一个0用于第一个数的归并时固定左边的一个端点右边有两个指针进行遍历查找
核心代码段 int i l, jlo mid1, jup mid1;//右侧两个指针while(i mid)//遍历左侧的端点{ while(jlo r sum[jlo]-sum[i] lower)//[i,jlo]不在范围内jlo;while(jup r sum[jup]-sum[i] upper)//[i,jup]在范围内jup;//最后 [jlo,jup) 为在范围内的右端点count jup-jlo;//计数i;//遍历下一个左端点}class Solution {vectorlong temp;
public:int countRangeSum(vectorint nums, int lower, int upper) {if(nums.size() 0)return 0;vectorlong sum(nums.size()1, 0);temp.resize(nums.size()1);for(int i 1; i sum.size(); i)sum[i] sum[i-1] nums[i-1];return mergeSort(sum,0,sum.size()-1,lower,upper);}int mergeSort(vectorlong sum, int l, int r, int lower, int upper){if(l r)return 0;int mid l((r-l)1), count 0;count mergeSort(sum, l, mid, lower, upper);count mergeSort(sum, mid1, r, lower, upper);int i l, jlo mid1, jup mid1;while(i mid){while(jlo r sum[jlo]-sum[i] lower)jlo;while(jup r sum[jup]-sum[i] upper)jup;count jup-jlo;i;}//合并跟归并排序一致i l; int j mid1, k 0;while(i mid j r){if(sum[i] sum[j])temp[k] sum[i];elsetemp[k] sum[j];}if(i mid)while(i mid)temp[k] sum[i];elsewhile(j r)temp[k] sum[j];for(i 0; i k; i)sum[l] temp[i];return count;}
};28 ms 12.2 MB
