[数据结构与算法]前缀和专题

理论

存在一个数组nums[]:
它在第0个位置的前缀和，就是nums[0]
它在第1个位置的前缀和，就是nums[0] + nums[1]
它的第i个位置的前缀和，就是nums[0] + nums[1] + ··· + nums[i - 1] + nums[i]
从第0个位置到第nums.length - 1个位置，每一个位置都对应了一个前缀和，这样的一系列前缀和，就称为前缀和数组

对于前缀和数组，从经验上处理，一般将它的长度设为 原数组长度 + 1，即，在代码上表示，为
int[] prefixSum = new int[nums.length + 1];
nums[i]的前缀和为prefixSum[i + 1]:
第0个位置的前缀和，就是prefixSum[0 + 1] = prefixSum[1] (nums[0])
第1个位置的前缀和，就是prefixSum[1 + 1] = prefixSum[2] (nums[0] + nums[1])
第i个位置的前缀和，就是prefixSum[i + 1] (nums[0] + ··· + nums[i])

前缀和数组用于解决连续子数组求和(积)问题，使用时有两个要求:
1.必须是连续子数组，不能对原数组排序，否则会打乱数组顺序，也不能跳着选数据
2.用于解决子数组的求和或求积问题

例如，求数组[i, j]范围内的和
根据前缀和，可以这样考虑问题，先求数组从[0, i - 1]范围内的和，它的和加上[i, j]范围内的和，就是数组从[0, j]范围内的和
即 Sum[0, i - 1] + Sum[i, j] = Sum[0, j]
反过来想，如果我知道了数组从[0, i - 1]范围内的和，以及数组从[0, j]范围内的和，那么我就可以求出数组[i, j]范围内的和
相当于将上面的等式移项 Sum[0, j] - Sum[0, i - 1] = Sum[i, j]
而Sum[0, j]为第j个位置的前缀和，prefixSum[j + 1]; Sum[0, i - 1]为第i - 1个位置的前缀和，为prefixSum[(i - 1) + 1]，即prefixSum[i]
代入上式，有prefixSum[j + 1] - prefixSum[i] = Sum[i, j]
这就是前缀和的通解

实践

724. 寻找数组的中心下标
难度: 简单

这道题的意思，就是在数组nums中找到一个数，这个数在数组中的位置是i，需要满足Sum[0, i - 1] == Sum[i + 1, nums.length - 1]，即，这个数左边所有的数加起来等于右边所有的数加起来，显然可以通过前缀和来求解

class Solution {
    public int pivotIndex(int[] nums) {
        int[] prefixSum = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        // 根据题意，设中心下标为i，左边的和为prefixSum[i]，右边的和为prefixSum[nums.length] - prefixSum[i + 1]
        for (int i = 0; i < nums.length; i++) {
            if (prefixSum[nums.length] - prefixSum[i + 1] == prefixSum[i]) return i;
        }
        return -1;
    }
}

560. 和为 K 的子数组
难度: 中等

本题相当于，已知prefixSum[j + 1]，和[i, j]的和，求有几个prefixSum[i]能匹配

class Solution {
    public int subarraySum(int[] nums, int k) {
        int[] prefixSum = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        // key代表prefixSum的值，value代表值出现的次数
        HashMap<Integer, Integer> map = new HashMap<>();
        int count = 0;
        // 0代表当前的前缀和的值刚好等于k，所以完全减完
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            // map中有符合条件的前缀和，获取其次数
            count += map.getOrDefault(prefixSum[i + 1] - k, 0);
            map.put(prefixSum[i + 1], map.getOrDefault(prefixSum[i + 1], 0) + 1);
        }
        return count;
    }
}

1248. 统计「优美子数组」
难度: 中等

本题需要一定的技巧，将 奇数统计问题 转换为 和为k的子数组 问题

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        // 将奇数置为1，偶数置为0，统计奇数个数k相当于前缀和之差为k的个数
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] % 2 == 1) {
                nums[i] = 1;
            } else {
                nums[i] = 0;
            }
        }
        // 求前缀和数组
        int[] prefixSum = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        int count = 0;
        // 刚好减完的情况
        map.put(0, 1);
        // 求复合条件的前缀和的数量
        for (int i = 0; i < nums.length; i++) {
            count += map.getOrDefault(prefixSum[i + 1] - k, 0);
            map.put(prefixSum[i + 1], map.getOrDefault(prefixSum[i + 1], 0) +);
        }
        return count;
    }
}

974. 和可被 K 整除的子数组
难度: 中等

本题需要用到同余定理 若(a - b)能被m整除，那么a % m == b % m，反之亦然(充分必要)
在java语言中，如果需要数学上的余运算，需要Math.floorMod()函数(直接使用%运算符可能会出错)

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int count = 0;
        int[] prefixSum = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            // 同余定理
            int remainder = Math.floorMod(prefixSum[i + 1], k);
            count += map.getOrDefault(remainder, 0);
            map.put(remainder, map.getOrDefault(remainder, 0) + 1);
        }
        return count;
    }
}