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 位 的整数

二、解题思路

1. 首先计算前缀和数组，前缀和数组的第 i 个元素表示 nums 数组从下标 0 到下标 i-1 的元素之和。这样，区间和 S(i, j) 可以通过前缀和数组快速计算得到，即 S(i, j) = prefixSum[j+1] - prefixSum[i]。

2. 使用归并排序的思想来解决这个问题。在归并排序的过程中，统计满足条件的区间和的个数。

3. 在归并排序的合并过程中，对于左半部分的每一个前缀和，找到右半部分中满足 lower <= prefixSum[j] - prefixSum[i] <= upper 的前缀和的个数。

4. 最终统计满足条件的区间和的个数。

三、具体代码

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 语句来处理不同的情况，例如当左半部分的指针超过边界时，只需要处理右半部分。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。