327.区间和的个数

题目描述

题解

前缀和数组为sum[];
满足条件的区间和为：
lower <= sum[i] - sum[j] <= upper;
将上述式子变形得到：
sum[i] - upper <= sum[j] <= sum[i] - lower;
也就是说在前缀和数组sum[0…i]中，满足上述条件的sum[j]都对应着一个满足条件的区间。

public int countRangeSum(int[] nums, int lower, int upper) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    TreeMap<Long, Integer> tree = new TreeMap<>();
    tree.put(0L, 1);

    int count = 0;
    long sum = 0L;
    for (int num : nums) {
        sum += num;
        for (int cnt : tree.subMap(sum - upper, true, sum - lower, true).values()) {
            count += cnt;
        }
        tree.put(sum, tree.getOrDefault(sum, 0) + 1);
    }

    return count;
}