alleyf

应用场景

主要适用的场景是原始数组不会被修改的情况下，前缀和技巧适用于快速、频繁地计算一个索引区间内的元素之和。

框架模板

class NumArray {
    // 前缀和数组
    private int[] preSum;

    // 输入一个数组，构造前缀和
    public NumArray(int[] nums) {
        // preSum[0] = 0，便于计算累加和
        preSum = new int[nums.length + 1];
        // 计算 nums 的累加和
        for (int i = 1; i < preSum.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
    }

    // 查询闭区间 [left, right] 的累加和
    public int sumRange(int left, int right) {
        return preSum[right + 1] - preSum[left];
    }
}

算法步骤

1. 构造函数时预计算前缀和（前缀和数组的大小等于源数组大小+1，索引i表示前i个元素的前缀和）
2. 根据区间查询前缀和数组得到区间值（左边界不变，右边界+1）