前缀和

525. 连续数组

Map map 作为该前缀和第一次出现的位置，遍历前缀和时寻找当前前缀和上一次出现时的位置，进行下标相减即为长度

由于找答案的过程是一个单调过程，前缀和数组遍历时只会利用前面的前缀和，因此可以对其进行压缩。

使用一个sum变量替换前缀数组，在每次循环的时候同时进行答案的寻找和前缀和的计算。

由于前缀和数组一般是原数组大小+1，sum[i] = num[0]+……+num[i-1]，因此在每次循环到i时，要先处理sum，此时sum代表的是num[0]+……+num[i-1]，进行处理之后，再sum+=num[i] == num[0]+……+num[i-1]+num[i]

注意如果使用前缀和数组和原数组对齐的方式（preSum[i]代表包含了nums[i]的前缀和），两个数组的下标要对齐，所以在map维护的时候，sum是i-1时的sum，因此map维护时下标要记为i-1，如下代码块1

如果如果使用前缀和数组和原数组错开一位的方式（preSum[i]代表不包含nums[i]的前缀和），前缀和数组的下标是nums的下标+1，因此在map维护的时候，i为num[i-1]的前缀和下标，而在进行ans求值时，由于当前的i代表nums[i]，而我们要用的是前缀和的下标，因此是i+1，即1 + i - map.get(sum)才是真正的数组长度，如代码块2

class Solution {
    public int findMaxLength(int[] nums) {
        int sum = 0 , ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            // 这时候的sum是sum[i-1]，注意是对齐方式，sum有-1位置
            if (!map.containsKey(sum)) map.put(sum,i-1);
            // 下面操作会将sum更新到sum[i]
            sum = sum + (nums[i] == 1 ? 1 : -1);
            if (map.containsKey(sum)) ans = Math.max(ans,i - map.get(sum));
        }
        return ans;
    }
}
class Solution {
    public int findMaxLength(int[] nums) {
        int sum = 0 , ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            //这时候是sum[i]
            if (!map.containsKey(sum)) map.put(sum,i);
            sum = sum + (nums[i] == 1 ? 1 : -1);
            // 上面加了后就变成了sum[i+1]了，所以下面算索引的时候要用i+1来算
            if (map.containsKey(sum)) ans = Math.max(ans,1+i - map.get(sum));
        }
        return ans;
    }
}