给定一个整数数组 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。
思路:
首先忽略题目中的复杂度说明,使用两层遍历枚举所有区间的,统计枚举的区间和满足要求的数量
抛砖引玉
/**
* @param {number[]} nums
* @param {number} lower
* @param {number} upper
* @return {number}
*/
var countRangeSum = function(nums, lower, upper) {
let _result = 0
for (let i = 0; i < nums.length; i++) {
// 区间和
let item = 0
for (let j = i; j < nums.length; j++) {
item = item + nums[j]
if (item >= lower && item <= upper) _result++
}
}
return _result
};
归并排序是用于两个有序序列和并成一个有序序列的算分。
在本题中,考察的是数组子集的和是否在lower、upper之间,可先遍历nums求出其前缀和sum:0,nums[0],nums[0]+nums[1],nums[0]+nums[1]+nums[2]...
var countRangeSum = function (nums, lower, upper) {
// 前缀元素和
let sum = [0]
for (let i = 1;i <= nums.length;i++) {
sum[i] = sum[i - 1] + nums[i - 1]
}
function helper (left, right) {
if (left === right) return 0
let mid = Math.floor((left + right) / 2),
// 先递归切分区间
result = helper(left, mid) + helper(mid + 1, right);
// 统计left到right之前满足条件的下标组合数量
let index = left,
l = mid + 1,
r = mid + 1;
while (index <= mid) {
while (l <= right && sum[l] - sum[index] < lower) l++;
while (r <= right && sum[r] - sum[index] <= upper) r++;
result += (r - l);
index++;
}
// 两个合并子树形成一个有序数组,保证后续切分的数组均为有序数组
let sorted = Array(right - left + 1),
p1 = left,
p2 = mid + 1,
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 (let i = 0; i < sorted.length; i++) {
sum[left + i] = sorted[i];
}
return result;
}
return helper(0, sum.length - 1);
};