Leetcode525 Contiguous Array

Posted on In

题目描述

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

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

1
2
3
Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

解析

这是一个题目描述得特别简单的题，不过思路比较tricky，题目要求求一个只含0和1的数组中最长的，含有相同数量0和1的子数组的长度，暴力法O(n^2)遍历所有子数组，这个不难想到，不过题目说数组长度会有50000，有大概率会超时。

一个Tricky的方法是遍历数组一次，设置一个count，每次遇到1则加一，遇到0则减一，如果同样的count出现两次，则两个index之间的0和1出现次数相等，有一点统计出现一半以上的数字那道题的感觉，也是遇到+1，没有遇到-1，Leetcode官方题解里有一个图很好地说明了这个intuition的原理:

这里我们需要用一个HashMap存储count与第一次出现该count的index的对应关系，便于日后查找, 具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int findMaxLength(int[] nums) {
    HashMap<Integer, Integer> map = new HashMap<>();
    map.put(0,-1);
    int sum = 0;
    int res = 0;
    for(int i = 0; i < nums.length; i++){
        sum += nums[i] == 1 ? 1 : -1;
        if(map.containsKey(sum))
            res = Math.max(res, i - map.get(sum));
        else
            map.put(sum, i);
    }
    return res;
}

总结

一个描述十分简单的题目，很有意思的一个小技巧，从O(N^2)到O(N)的优化，挺适合作为面试题，不过如果以前没有见过这个技巧，可能很难再面试时期想出，所以，还是要多刷题呀~~