LeetCode 327. 区间和的个数

Categories:

题目描述
思路分析
1. 解法一：前缀和 + 归并排序（推荐）
相似题目

题目描述

✅ 327. 区间和的个数

思路分析

解法一：前缀和 + 归并排序（推荐）

核心思路：

计算前缀和数组 pre。

在归并排序过程中统计满足 lower <= pre[j] - pre[i] <= upper 的对数。

同时完成排序以保证统计有序性。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示数组长度。

空间复杂度：O(n)，用于辅助数组。

class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        long[] pre = new long[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            pre[i + 1] = pre[i] + nums[i];
        }
        return mergeCount(pre, 0, pre.length, lower, upper);
    }

    private int mergeCount(long[] pre, int left, int right, int lower, int upper) {
        if (right - left <= 1) {
            return 0;
        }

        int mid = left + (right - left) / 2;
        int count = mergeCount(pre, left, mid, lower, upper)
                + mergeCount(pre, mid, right, lower, upper);

        int i = mid;
        int j = mid;
        for (int l = left; l < mid; l++) {
            while (i < right && pre[i] - pre[l] < lower) {
                i++;
            }
            while (j < right && pre[j] - pre[l] <= upper) {
                j++;
            }
            count += j - i;
        }

        long[] tmp = new long[right - left];
        int p1 = left;
        int p2 = mid;
        int p = 0;
        while (p1 < mid && p2 < right) {
            if (pre[p1] <= pre[p2]) {
                tmp[p++] = pre[p1++];
            } else {
                tmp[p++] = pre[p2++];
            }
        }
        while (p1 < mid) {
            tmp[p++] = pre[p1++];
        }
        while (p2 < right) {
            tmp[p++] = pre[p2++];
        }
        System.arraycopy(tmp, 0, pre, left, tmp.length);

        return count;
    }
}

func countRangeSum(nums []int, lower int, upper int) int {
	pre := make([]int64, len(nums)+1)
	for i := 0; i < len(nums); i++ {
		pre[i+1] = pre[i] + int64(nums[i])
	}
	return mergeCount(pre, 0, len(pre), int64(lower), int64(upper))
}

func mergeCount(pre []int64, left int, right int, lower int64, upper int64) int {
	if right-left <= 1 {
		return 0
	}

	mid := left + (right-left)/2
	count := mergeCount(pre, left, mid, lower, upper) + mergeCount(pre, mid, right, lower, upper)

	i, j := mid, mid
	for l := left; l < mid; l++ {
		for i < right && pre[i]-pre[l] < lower {
			i++
		}
		for j < right && pre[j]-pre[l] <= upper {
			j++
		}
		count += j - i
	}

	tmp := make([]int64, right-left)
	p1, p2, p := left, mid, 0
	for p1 < mid && p2 < right {
		if pre[p1] <= pre[p2] {
			tmp[p] = pre[p1]
			p1++
		} else {
			tmp[p] = pre[p2]
			p2++
		}
		p++
	}
	for p1 < mid {
		tmp[p] = pre[p1]
		p1++
		p++
	}
	for p2 < right {
		tmp[p] = pre[p2]
		p2++
		p++
	}
	copy(pre[left:right], tmp)

	return count
}

相似题目

题目	难度	考察点
327. 区间和的个数	困难	归并排序
315. 计算右侧小于当前元素的个数	困难	归并排序
493. 翻转对	困难	归并排序
53. 最大子数组和	简单	前缀和
560. 和为 K 的子数组	中等	前缀和

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/70753266