剑指offer

剑指offer011-0和1个数相同的子数组

和1个数相同的子数组

Posted by 高明 on 2020-01-01

剑指offer011-0和1个数相同的子数组

题目

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

 

示例 1:

输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

示例 2:

输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。

 

提示：

  • 1 <= nums.length <= 105
  • nums[i] 不是 0 就是 1

 

注意：本题与主站 525 题相同： https://leetcode-cn.com/problems/contiguous-array/

Related Topics
  • 数组
  • 哈希表
  • 前缀和

  • 👍 20
  • 👎 0

    • 思路

    这个用前缀和，这种题目可以抽象出一个模板，两数之差

    还是如剑指offer010所描述，我们可以保存一个前缀和数组

    比如0,0,1,0,0,0,1,1

    初始化数组sum，sum[i]表示0~i-1的和

    即

    0 0 0 1 1 1 1 2 2

    我们考虑arr的子数组如何满足条件，即子数组0和1一直样多

    很明显，对于0,0,1,1，如果要满足0的个数和1的个数一样多，只要满足 2*sum(0,0,1,1) = 数的个数 = 4

    即2*(sum[j] - sum[i]) = j-(i+1)+1

    因为sum[j]是 0-j，包含j

    sum[i]是0-i，包含i

    所以 sum[j] - sum[i] 是计算 i+1 ~j的和，他们的距离就是 j - (i+1) +1 = j - i

    因此，整个问题就变成了从数组sum中找到两个数满足

    2 * (sum[j] - sum[i]) = j - i

    变形一下就变成

    2sum[j] - j = 2sum[i] -i

    整个形式比较特殊，我们先按照一般的理解，2sum[j] - j -(2sum[i] -i) = 0

    我们不妨换元，即a =2sum[i] - i,b =2sum[j] - j

    也就是 a-b = 0

    又回到了两数之差等于定值0

    1
    2
    3
    4
    5
    6
    7
    8
    9
    for (int i = 0; i < sum.length; i++) {
        int a = 2 * sum[i] - i;
        int b = a - 0; // 两数之差
        if (map.containsKey(b)) {
            // 如果包含b
        }
        // 不管怎样，把a放进map，至于value按照题目的意思选择
        map.put(a, ?);
    }

    在结合题目的意思，我们要求最大的范围，也就是当a进入map的时候，我们要保存a的index，当a再次进入map的时候，我们取最小值，【实际上不需要操作，因为前面a的index肯定小于后面】

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    Map<Integer, Integer> map = new HashMap<>();
    int count = Integer.MIN_VALUE;
    int m = Integer.MAX_VALUE;
    for (int i = 0; i < sum.length; i++) {
        int a = 2 * sum[i] - i;
        int b = a;
        if (map.containsKey(b)) {
            count = Math.max(i - map.get(b), count);
        }
        map.put(a, Math.min(i, map.getOrDefault(a, m))); // 这边保存index的最小值，即期望 j-i 取得最大值
    }
    return count == Integer.MIN_VALUE ? 0: count;

    【实际上不需要操作，因为前面a的index肯定小于后面】

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution {
        public int findMaxLength(int[] nums) {
            int[] sum = new int[nums.length + 1];
            for (int i = 1; i < sum.length; i++) {
                sum[i] = sum[i - 1] + nums[i - 1];
            }
            Map<Integer, Integer> map = new HashMap<>();
            int count = Integer.MIN_VALUE;
            for (int i = 0; i < sum.length; i++) {
                int a = 2 * sum[i] - i;
                if (map.containsKey(a)) {
                    count = Math.max(i - map.get(a), count);
                }else{
                    map.put(a, i);
                }

            }
            return count == Integer.MIN_VALUE ? 0: count;
        }
    }
    FEATURED TAGS
    剑指offer
    FRIENDS