一、题目

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

点击查看原题

二、思路

1）前缀和+哈希表

题意容易混淆，需注意理解。
相同数量的0和1最长连续子数组，这句话意思是子数组连续，但其中的0和1不一定连续（也就是内部是怎样的排列都可以），只要数量相等。
假设连续子数组在[i, j]区间，使用暴力法需要穷举该区间，时间复杂度肯定超。
使用前缀和可以O(1)时间获取[i, j]区间的和，记录为sum[j]-sum[i]，将nums中的0看作-1，那么当相同数量的0和1时，sum[j]-sum[i]=0，即sum[j]=sum[i].使用哈希表，根据sum[j]查找sum[i]就可以。

三、代码

1）前缀和+哈希表

  1. class Solution {
  2.     public int findMaxLength(int[] nums) {
  3.         int[] sum = new int[nums.length + 1];
  4.         for (int i = 0; i < nums.length; i++) {
  5.             sum[i+1] = sum[i] + (nums[i] == 0 ? -1 : 1);
  6.         }
  7.         Map<Integer, Integer> map = new HashMap();
  8.         int ans = 0;
  9.         for (int i = 2; i < sum.length; i++) {
  10.             // 如果之前存过同样的元素，就不存（即取最远的那个值，使连续子数组长度最长）
  11.             if (!map.containsKey(sum[i-2])) {
  12.                 map.put(sum[i-2], i-2);
  13.             }
  14.             if (map.containsKey(sum[i])) {
  15.                 ans = Math.max(ans, i - map.get(sum[i]));
  16.             }
  17.         }
  18.         return ans;
  19.     }
  20. }

时间复杂度为O(n)，空间复杂度为O(n)。