剑指 Offer II 011. 0 和 1 个数相同的子数组

前缀和 + HashMap

  1. 问题：为什么在 HashMap 找到相同的前缀和就能表示找到了一串连续数组呢? 假如 hashMap 存储 -1 的值索引值为 i，当前索引值为 j，
    那么区间 [i + 1, j] 的前缀和为 0，这是我们要求的连续数组，所以就可以从 hashmap 中取出 -1 的索引值构成连续数组。
  2. base case 包含 (0, -1) 这种情况，否则计算出错。
  3. 向这种前缀和 + HashMap 主要的思想就是当 [0,i] 的前缀和等于 [0, j] 的前缀和时， [i+1, j] 这一部分区间的特性。比如这一题当遇到 0 时就比较巧妙，
    这样就使得前面条件成立时，区间[i + 1, j] 的前缀和为0。 ```java
  1. class Solution {
  2.     public int findMaxLength(int[] nums) {
  3.         if (nums == null || nums.length == 0) return 0;
  4.         int sum = 0, maxLen = 0;
  5.         Map<Integer, Integer> index = new HashMap<>();
  6.         // base case
  7.         index.put(0, -1);
  8.         for (int i = 0; i < nums.length; i++) {
  9.             if (nums[i] == 0) {
  10.                 sum -= 1;
  11.             } else {
  12.                 sum += 1;
  13.             }
  14.             if (index.containsKey(sum)) {
  15.                 maxLen = Math.max(maxLen, i - index.get(sum));
  16.             } else {
  17.                 index.put(sum, i);
  18.             }
  19.         }
  20.         return maxLen;
  21.     }
  22. }

```