区间和的个数
难度:
标签:
题目描述
给你一个整数数组 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 位 的整数
代码结果
运行时间: 704 ms, 内存: 32.1 MB
/*
Solution Approach using Java Streams:
1. Convert the array `nums` into a list of prefix sums.
2. Use streams to filter and count the number of valid subarrays within the range [lower, upper].
*/
import java.util.stream.IntStream;
public class Solution {
public int countRangeSum(int[] nums, int lower, int upper) {
long[] prefixSum = new long[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
return (int) IntStream.range(0, nums.length)
.flatMap(i -> IntStream.range(i + 1, nums.length + 1)
.filter(j -> {
long sum = prefixSum[j] - prefixSum[i];
return sum >= lower && sum <= upper;
}))
.count();
}
}解释
方法:
该题解采用分治法与归并排序的思想来解决问题。首先，我们计算了数组的前缀和，然后通过递归分治方法处理每个子数组，并在合并的过程中统计符合条件的区间和的个数。具体步骤如下：
1. 计算数组的前缀和，以便快速计算任意子数组的和。
2. 使用递归分治的方法来处理和合并子数组。对于每个子问题，如果它只包含一个元素，直接判断这个单独元素形成的区间和是否在指定范围内。
3. 在合并两个已经排序的子数组的过程中，使用双指针技术统计当前右侧元素与左侧元素组合形成的区间和落在[lower, upper]范围内的个数。
4. 合并完成后，还需要将左右两部分归并排序，以便后续操作可以继续利用已排序的性质加速区间和的计算。
时间复杂度:
O(n log n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在计算区间和的个数时选择使用前缀和而不是直接遍历所有可能的区间组合？
▷🦆
分治法在这个问题中具体是如何实现的？能否详细解释其在合并步骤中的作用和机制？
▷🦆
在合并过程中使用双指针统计符合条件的区间和的数量，这种方法的时间复杂度是多少？
▷相关问题
计算右侧小于当前元素的个数
给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例 1：
输入：nums = [5,2,6,1]
输出：[2,1,1,0]
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素
示例 2：
输入：nums = [-1] 输出：[0]
示例 3：
输入：nums = [-1,-1] 输出：[0,0]
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104