Java 算法：前缀和进阶应用

题目一：除自身以外数组的乘积

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] pre = new int[len];
        int[] last = new int[len];
        int[] ret = new int[len];
        pre[0] = 1;
        last[len-1] = 1;
        for(int i = 1; i < len; i++) {
            pre[i] = pre[i-1] * nums[i-1];
        }
        for(int i = len-2; i >= 0; i--) {
            last[i] = last[i+1] * nums[i+1];
        }
        for(int i = 0; i < len; i++) {
            ret[i] = last[i] * pre[i];
        }
        return ret;
    }
}

前缀积：pre[i] 表示下标 i 左侧所有元素的乘积（不包含 nums[i]）。 后缀积：last[i] 表示下标 i 右侧所有元素的乘积（不包含 nums[i]）。 除当前下标外所有元素乘积：ret[i] = pre[i] * last[i]。

题目二：和为 K 的子数组

解法一：暴力枚举

class Solution {
    public int subarraySum(int[] nums, int k) {
        int len = nums.length;
        int count = 0;
        for(int i = 0; i < len; i++) {
            int sum = 0;
            for(int j = i; j < len; j++) {
                sum += nums[j];
                if(sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
}

两层循环枚举了所有的情况，sum 累加 nums[j] 动态计算 nums[i] 到 nums[j] 的和，不重不漏。

解法二：前缀和 + 哈希表

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> hash = new HashMap<>();
        int len = nums.length;
        int sum = 0, ret = 0;
        hash.put(0, 1);
        for(int i = 0; i < len; i++) {
            sum += nums[i];
            ret += hash.getOrDefault(sum - k, 0);
            hash.put(sum, hash.getOrDefault(sum, 0) + 1);
        }
        return ret;
    }
}

注意：

1. 需要初始化 hash[0] = 1，如果没有初始化，当第一个元素等于 k 时，会漏掉这次计数。
2. 先查 hash 表再更新哈希表。

题目三：和可被 K 整除的子数组

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer, Integer> hash = new HashMap<>();
        int sum = 0, ret = 0;
        hash.put(0, 1);
        for(int x : nums) {
            sum += x;
            int modulus = (sum % k + k) % k;
            ret += hash.getOrDefault(modulus, 0);
            hash.put(modulus, hash.getOrDefault(modulus, 0) + 1);
        }
        return ret;
    }
}

补充：

1. 通过同余定理可得：(sum - 某一前缀和) 得到子数组元素之和，要找 (sum - 前缀和) % k = 0；即 sum % k = 某一前缀和 % k；如果此时哈希表中正好存的是余数，就可以直接查询。
2. 处理负数求余数，在 Java 中余数的符号由第一个操作数的符号决定，所以在求余数时需要经过以下处理：(sum % k + k) % k。解释如下：第一次求余数如果是负数，且这个负数的绝对值小于 k，那么加上一个 k 之后就会得到正数，再取余数就完成操作。

算法原理同上题。

题目四：连续数组

class Solution {
    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> hash = new HashMap<>();
        hash.put(0, -1);
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == 0) {
                nums[i] = -1;
            }
        }
        int sum = 0;
        int ret = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if(hash.containsKey(sum)) {
                ret = Math.max(i - hash.get(sum), ret);
            } else {
                hash.put(sum, i);
            }
        }
        return ret;
    }
}

算法原理：

1. 将所有的 0 转化为 -1，这样就能把求相同数量的 0、1 转化为求子数组元素之和为 0。
2. 每计算一个前缀和，如果这个前缀和在哈希表中，说明这两个下标之间的元素之和为 0，并且更新最大长度；如果不在哈希表中，就存入前缀和和下标。
3. 细节问题：如何处理第一个数就为 0 的情况；hash.put(0, -1)，此时如果第一个元素就为 0，长度就为 0 - (-1) = 1，符合题意。