难度:Hard
题目:
给你一个整数数组
nums
以及两个整数lower
和upper
。求数组中,值位于范围[lower, upper]
(包含lower
和upper
)之内的 区间和的个数 。区间和
S(i, j)
表示在nums
中,位置从i
到j
的元素之和,包含i
和j
(i
≤j
)。
示例 1:
输入:nums = [-2,5,-1], lower = -2, upper = 2 输出:3 解释:存在三个区间:[0,0]、[2,2] 和 [0,2] ,对应的区间和分别是:-2 、-1 、2 。
示例 2:
输入:nums = [0], lower = 0, upper = 0 输出:1
提示:
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
-105 <= lower <= upper <= 105
- 题目数据保证答案是一个 32 位 的整数
Related Topics
- 树状数组
- 线段树
- 数组
- 二分查找
- 分治
- 有序集合
- 归并排序
重点!!!解题思路
明确解题思路:
(1)题目要求求出区间和,根据区间和即可想到前缀和
(2)那么将此题简化,前缀和相减即为区间和,这样即可列出一个式子:假设前缀和数组为nums,那么区间和为nums[j]-nums[i],加上区间和范围即lower<=nums[j]-nums[i]<=upper
(3)式子继续简化nums[j]-lower>=nums[i]>=nums[j]-upper,通过式子可以看出如果我们能固定j的位置即可求出i的位置范围a<=nums[i]<=b
(4)这样通过找到a和b的范围,即可确定在a和b的区间和个数为b-a+1
(5)如果想j再往后走一位,这时如果nums[j+1]>nums[j] 那么根据公式我们nums[j+1]的a和b一定大于nums[j]的a和b
(6)那么我们如何保证nums[j+1]一定大于nums[j]呢 这时我们就可以联想到归并排序了,因为归并排序的时候就是先分开递归再并在一起排序
(7)明白以上思路 即可做题了
源码+讲解:
class Solution {
long[] temp;
public int countRangeSum(int[] nums, int lower, int upper) {
long[] sum = new long[nums.length + 1];
temp = new long[nums.length + 1];
sum[0] = 0;
for (int i = 0; i < nums.length; i++) sum[i + 1] = sum[i] + nums[i]; //求一个前缀和数组
return merge_sort(sum, 0, sum.length - 1, lower, upper); //我们归并排序的就是一个前缀和数组
}
//这里就是一个很基础的归并排序,不懂得朋友请看本章节的其他题巩固一下
public int merge_sort(long[] sum, int l, int r, int lower, int upper) {
if (l >= r) return 0;
int mid = (l + r) >> 1, ans = 0;
ans += merge_sort(sum, l, mid, lower, upper);
ans += merge_sort(sum, mid + 1, r, lower, upper);
ans += countTwoPart(sum, l, mid, mid + 1, r, lower, upper); //在合并前进行区间和个数的判断
int k = l, p1 = l, p2 = mid + 1;
while (p1 <= mid || p2 <= r) {
if (p2 > r || (p1 <= mid && sum[p1] < sum[p2])) {
temp[k++] = sum[p1++];
} else {
temp[k++] = sum[p2++];
}
}
for (int i = l; i <= r; i++) sum[i] = temp[i];
return ans;
}
public int countTwoPart(long[] sum, int l1, int r1, int l2, int r2, int lower, int upper) {
int k1 = l1, k2 = l1, ans = 0;
for (int j = l2; j <= r2; j++) { //通过固定模拟nums[j]的位置来计算k1,k2的边界
long a = sum[j] - upper;
long b = sum[j] - lower;
while (k1 <= r1 && sum[k1] < a) k1++; //k1移动到a的位置
while (k2 <= r1 && sum[k2] <= b) k2++; //k2移动到b+1的位置
ans += k2 - k1; //得到k1,k2的边界,其中k1-k2就是区间和个数
}
return ans;
}
}
运行结果:
如果您还有什么疑问或解答有问题,可在下方评论,我会及时回复。文章来源:https://www.toymoban.com/news/detail-610076.html
系列持续更新中,点个订阅吧,喜欢练习算法那就点个攒吧 文章来源地址https://www.toymoban.com/news/detail-610076.html
到了这里,关于LeetCode[327]区间和的个数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!