Java实现 LeetCode 327 区间和的个数
2023-09-14 08:58:05 时间
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。
class Solution {
public int countRangeSum(int[] nums, long lower, long upper) {
long sums[] = new long[nums.length];
for (int i=0; i<nums.length; i++) {
sums[i] = ((i-1 >= 0) ? sums[i-1] : 0) + nums[i];
}
//System.out.println(Arrays.toString(sums));
int result = divideAndConquer(sums, 0, sums.length-1, upper, lower);
return result;
}
private int divideAndConquer(long sums[], int start, int end, long upper, long lower) {
if (start > end) return 0;
if (start == end) return (sums[start] <= upper && sums[start] >= lower) ? 1 : 0;
int mid = (start+end)/2;
int counts = 0;
counts += divideAndConquer(sums, start, mid, upper, lower);
counts += divideAndConquer(sums, mid+1, end, upper, lower);
int ls = start, le=mid;
while (le >= start && sums[mid+1] - sums[le] <= upper) le--;
for (int r=mid+1; r<=end; r++) {
while (ls <= mid && sums[r] - sums[ls] >= lower) ls++;
while (le+1 <= mid && sums[r] - sums[le+1] > upper ) le++;
if (ls - le -1 < 0) continue;
counts += (ls-le-1);
}
ls = start;
int i = 0, r= mid+1;
long merged[] = new long[end-start+1];
while (ls <= mid || r <= end) {
if (ls > mid || (r<=end && sums[r] < sums[ls])) {
merged[i++] = sums[r++];
} else {
merged[i++] = sums[ls++];
}
}
for (i=0; i<merged.length; i++) {
sums[start+i] = merged[i];
}
//System.out.println(Arrays.toString(sums) + " " + counts + "," + start + "-" + end);
return counts;
}
}
相关文章
- Java实现 LeetCode 762 二进制表示中质数个计算置位(位运算+JDK的方法)
- Java实现 LeetCode 706 设计哈希映射(数组+链表)
- Java实现 LeetCode 705 设计哈希集合(使用数组保存有没有被用过)
- Java实现 LeetCode 699 掉落的方块(线段树?)
- Java实现 LeetCode 678 有效的括号字符串(暴力+思路转换)
- Java实现 LeetCode 673 最长递增子序列的个数(递推)
- Java实现 LeetCode 670 最大交换(暴力)
- Java实现 LeetCode 541 反转字符串 II(暴力大法)
- Java实现 LeetCode 509 斐波那契数
- Java实现 LeetCode 450 删除二叉搜索树中的节点
- Java实现 LeetCode 449 序列化和反序列化二叉搜索树
- Java实现 LeetCode 368 最大整除子集
- Java实现 LeetCode 335 路径交叉
- Java实现 LeetCode 97 交错字符串
- Java实现 LeetCode 29 两数相除
- Java实现LeetCode #986 - Interval List Intersections
- Java实现LeetCode_0020_ValidParentheses