连续数组open in new window

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

思路

1. 相同的 1 和 0 ，可以把0换为 -1 ，那么就是 连续的 1和-1 的和为 0 的子数组的长度
2. 是一个前缀和问题
3. 先计算任意前缀和的值，并利用哈希表记录下标和值。
4. 遍历数组。碰到1时 sum+1，碰到0 时 sum-1。
5. 判断sum值是否出现在哈希表上，如果是，比较当前下标和哈希表记录的下标的差与最大长度，取最大值。
6. 哈希表中没有，记录。

public class ContiguousArray {

    public static int findMaxLength(int[] nums) {
        Map<Integer, Integer> h = new HashMap<>();
        int max = 0;
        int sum = 0;
        h.put(sum, -1);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
                sum++;
            } else {
                sum--;
            }
            if (h.containsKey(sum)) {
                max = Math.max(max, i - h.get(sum));
            } else {
                h.put(sum, i);
            }
        }
        return max;
    }
    public static void main(String[] args) {
        System.out.println(findMaxLength(new int[]{0, 1, 1, 1, 0, 0, 0}));
    }
}

思路2

1. 因为是求连续相同的子数组最长的的长度，还可以用朴素的二次遍历的方法。
2. 思考过滑动窗口，但是并不知道行不通。