LeetCode题练习与总结：区间和的个数--327

一、题目描述

给你一个整数数组 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 <= 10^5
-2^31 <= nums[i] <= 2^31 - 1
-10^5 <= lower <= upper <= 10^5
题目数据保证答案是一个 32 位 的整数

二、解题思路

首先计算前缀和数组，前缀和数组的第 i 个元素表示 nums 数组从下标 0 到下标 i-1 的元素之和。这样，区间和 S(i, j) 可以通过前缀和数组快速计算得到，即 S(i, j) = prefixSum[j+1] - prefixSum[i]。
使用归并排序的思想来解决这个问题。在归并排序的过程中，统计满足条件的区间和的个数。
在归并排序的合并过程中，对于左半部分的每一个前缀和，找到右半部分中满足 lower <= prefixSum[j] - prefixSum[i] <= upper 的前缀和的个数。
最终统计满足条件的区间和的个数。

三、具体代码

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 mergeSort(prefixSum, 0, nums.length, lower, upper);}private int mergeSort(long[] prefixSum, int left, int right, int lower, int upper) {if (left >= right) {return 0;}int mid = left + (right - left) / 2;int count = mergeSort(prefixSum, left, mid, lower, upper) + mergeSort(prefixSum, mid + 1, right, lower, upper);int j = mid + 1, k = mid + 1;for (int i = left; i <= mid; i++) {while (j <= right && prefixSum[j] - prefixSum[i] < lower) j++;while (k <= right && prefixSum[k] - prefixSum[i] <= upper) k++;count += k - j;}long[] sorted = new long[right - left + 1];int p1 = left, p2 = mid + 1, p = 0;while (p1 <= mid || p2 <= right) {if (p1 > mid) {sorted[p++] = prefixSum[p2++];} else if (p2 > right) {sorted[p++] = prefixSum[p1++];} else {if (prefixSum[p1] <= prefixSum[p2]) {sorted[p++] = prefixSum[p1++];} else {sorted[p++] = prefixSum[p2++];}}}System.arraycopy(sorted, 0, prefixSum, left, sorted.length);return count;}
}

这段代码首先计算了前缀和数组，然后通过递归的方式使用归并排序来统计满足条件的区间和的个数。在合并过程中，通过双指针技巧找到满足条件的区间和。最终返回统计的结果。

四、时间复杂度和空间复杂度

1. 时间复杂度

计算前缀和数组 prefixSum 的时间复杂度是 O(n)，其中 n 是数组 nums 的长度。
mergeSort 方法是一个递归方法，它会将数组 prefixSum 分成两半，并对每一半递归地进行归并排序。
在每一层的递归中，我们需要合并两个已排序的子数组。合并过程中，对于左半部分的每一个前缀和，我们使用两个指针 j 和 k 来找到满足条件的区间和的个数，这个过程的时间复杂度是 O(n)。
因此，在每一层的递归中，我们需要 O(n) 的时间来合并数组，并且有 log(n) 层递归（因为每次递归都是将数组长度减半）。

综上所述，总的时间复杂度是 O(n log n)。

2. 空间复杂度

前缀和数组 prefixSum 占用 O(n) 的空间。
递归方法 mergeSort 的空间复杂度主要取决于递归的深度和临时数组 sorted。递归的深度是 O(log n)，而临时数组 sorted 在每一层递归中都是大小为 O(n)。

因此，总的空间复杂度是 O(n) + O(log n) * O(n) = O(n)。

五、总结知识点

前缀和数组：
- 用于快速计算任意子数组的和。
- 前缀和数组的第 i 个元素表示原数组从第 0 个元素到第 i-1 个元素的和。
归并排序：
- 利用分治策略将数组分成更小的部分进行排序，然后合并这些有序部分。
- 归并排序的时间复杂度是 O(n log n)，是一种稳定的排序算法。
递归：
- 递归是函数调用自身的一种方法。
- 在归并排序中，递归用于将问题分解为更小的子问题。
双指针技术：
- 在合并过程中，使用两个指针 j 和 k 来统计满足特定条件的区间和的数量。
- 通过移动指针，可以在 O(n) 时间内完成统计。
数组拷贝：
- 使用 System.arraycopy 方法来高效地复制数组中的元素。
- 这是 Java 标准库提供的一种优化过的数组复制方法。
边界检查：
- 在合并排序和统计区间和的过程中，代码中包含了对数组边界的检查，以避免数组越界。
逻辑判断：
- 使用 if-else 语句来处理不同的情况，例如当左半部分的指针超过边界时，只需要处理右半部分。