LeetCode 327. 区间和的个数
给定一个整数数组 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。 通过次数14,258提交次数35,378
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/count-of-range-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
今天这个 每日一题 太难了
答案 也很难， 找了一个动态规划 能通过
JS代码
/**
* @param {number[]} nums
* @param {number} lower
* @param {number} upper
* @return {number}
*/
var countRangeSum = function(nums, lower, upper, dp = 0, n = 0) {
for (var i = 0; i < nums.length; i++)
for (var j = i; j < nums.length; j++) {
dp = j === i ? nums[i] : dp + nums[j]
if (dp >= lower && dp <= upper) n++
}
return n
};个人理解，用数组存储
dp[i][j] 代表 从 i 加到 j 的和
思考后的 规律 if(i==j) dp[i][j]=num[i];
else if(j>i) )dp[i][j]=dp[i][j-1]+num[j];
判断是否满足 dp[i][j]是否在范围内 然后 n++;
因为 i是 相同的 优化空间
if(i==j) dp=num[i];
else if(j>i) )dp=dp+num[j];
判断是否满足 dp[i][j]是否在范围内 然后 n++;
还是 n方 的时间复杂度，但是具体细节加速了
c++ 超时了， js能过
class Solution {
public:
int countRangeSum(vector<int>& nums, int lower, int upper) {
int ans=0;
long long int dp=0;
int t=nums.size();
for(int i=0;i<t;i++){
for(int j=i;j<t;j++){
if(j==i) dp=nums[i];
else dp=dp+nums[j];
if(dp<=upper&&dp>=lower)ans++;
}
}
return ans;
}
};
从官方答案 抄过来的 归并算法
class Solution {
public:
int countRangeSumRecursive(vector<long>& sum, int lower, int upper, int left, int right) {
if (left == right) {
return 0;
} else {
int mid = (left + right) / 2;
int n1 = countRangeSumRecursive(sum, lower, upper, left, mid);
int n2 = countRangeSumRecursive(sum, lower, upper, mid + 1, right);
int ret = n1 + n2;
// 首先统计下标对的数量
int i = left;
int l = mid + 1;
int r = mid + 1;
while (i <= mid) {
while (l <= right && sum[l] - sum[i] < lower) l++;
while (r <= right && sum[r] - sum[i] <= upper) r++;
ret += (r - l);
i++;
}
// 随后合并两个排序数组
vector<int> sorted(right - left + 1);
int p1 = left, p2 = mid + 1;
int p = 0;
while (p1 <= mid || p2 <= right) {
if (p1 > mid) {
sorted[p++] = sum[p2++];
} else if (p2 > right) {
sorted[p++] = sum[p1++];
} else {
if (sum[p1] < sum[p2]) {
sorted[p++] = sum[p1++];
} else {
sorted[p++] = sum[p2++];
}
}
}
for (int i = 0; i < sorted.size(); i++) {
sum[left + i] = sorted[i];
}
return ret;
}
}
int countRangeSum(vector<int>& nums, int lower, int upper) {
long s = 0;
vector<long> sum{0};
for(auto& v: nums) {
s += v;
sum.push_back(s);
}
return countRangeSumRecursive(sum, lower, upper, 0, sum.size() - 1);
}
};int countRangeSum(vector<int>& nums, int lower, int upper) { long s = 0; vector<long> sum{0}; for(auto& v: nums) { s += v; sum.push_back(s); } return countRangeSumRecursive(sum, lower, upper, 0, sum.size() - 1); }
这个函数 就是把东西 放进 sum 表示 从 0 到 n 的 和
问题的 本质是 任意 i ，j
i<=j
lower<=sum[j]-sum[i]<upper
的 i j 个数
我们采用归并排序的方式，能够得到左右两个数组排序后的形式，以及对应的下标对数量。对于原数组而言，若要找出全部的下标对数量，只需要再额外找出左端点在左侧数组，同时右端点在右侧数组的下标对数量，而这正是我们此前讨论的问题。
作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/count-of-range-sum/solution/qu-jian-he-de-ge-shu-by-leetcode-solution/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
腾讯云开发者
