LeetCode 525. Contiguous Array

Problem

LeetCode 525. Contiguous Array

1. 题目简述

给出一个二进制数组，由0和1组成，找出最长的子数组，使得里面的0和1的数量相等。例如：

Example 1:
Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

2. 算法思路

这道题的思路很特别，我们需要记录一下。在这里将1看做是1，0看做是-1，然后我们记录前缀和（prefix sum），将每次前缀和都记录下来，如果发现有重复的前缀和，那么上一次出现的前缀和的位置到当前位置中0和1的数量应该是相等的，且我们只需要记录第一次出现的前缀和即可。

Hash Table

class Solution {
    public int findMaxLength(int[] nums) {
        int res = 0, sum = 0;
        Map<Integer, Integer> prefixSum = new HashMap();
        // 注意，这里要预先放一个sum为0的值，要不然后面计算和为0的时候会少算。
        prefixSum.put(0 , -1);

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
                sum++;
            } else {
                sum--;
            }

            if (!prefixSum.containsKey(sum)) {
                prefixSum.put(sum, i);
            } else {
                res = Math.max(res, i - prefixSum.get(sum));
            }
        }

        return res;
    }
}