算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
今天和大家聊的问题叫做 区间和的个数,我们先来看题面:
https://leetcode-cn.com/problems/count-of-range-sum/
Given an integer array nums and two integers lower and upper, return the number of range sums that lie in [lower, upper] inclusive. Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j inclusive, where i <= j.
给你一个整数数组 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
https://fanfanzhisu.blog.csdn.net/article/details/109544468
通过前缀树和分支排序处理
在排序过程中通过两两比对获取区间的和
由于是排序的只要找到符合要求区间的左右index,可以获取index之间的个数
public class Solution {
int res = 0;
int lower, upper;
long[] sums;
public int countRangeSum(int[] nums, int lower, int upper) {
this.lower = lower;
this.upper = upper;
sums = new long[nums.length+1];
for (int i = 0; i < nums.length; i++) {
sums[i+1] = sums[i] + nums[i];
}
sort(new long[sums.length], 0, nums.length);
return res;
}
private void sort (long[] tmp, int left, int right) {
if (left >= right) return;
int mid = (left + right) >>> 1;
sort(tmp, left, mid);
sort(tmp, mid + 1, right);
merge(tmp, left, mid ,right);
}
private void merge(long[] tmp, int left, int mid, int right) {
if (right + 1 - left >= 0) System.arraycopy(sums, left, tmp, left, right + 1 - left);
int i = left, j = mid + 1;
int low = mid + 1, up = mid + 1;
for (int k = left; k <= right; k++) {
// 找到[lower, upper] 的左index
while (low <= right && tmp[low] - tmp[i] < lower) low ++;
// 找到[lower, upper] 的右index
while (up <= right && tmp[up] - tmp[i] <= upper) up ++;
if (i > mid) {
sums[k] = tmp[j++];
} else if (j > right) {
sums[k] = tmp[i++];
res += up - low;
} else if (tmp[i] > tmp[j]) {
sums[k] = tmp[j++];
} else {
sums[k] = tmp[i++];
res += up - low;
}
}
}
}
class Test {
public static void main(String[] args) {
int[] nums = {-2147483647,0,-2147483647,2147483647};
// int[] nums = {-2,5,-1};
int lower = -564, upper = 3864;
Solution solution = new Solution();
System.out.println(solution.countRangeSum(nums, lower, upper));
}
}
好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。