编程之禅
0%

前缀和——找到含有相同数量 0 和 1 的最长连续子数组

发表于 更新于 分类于 阅读次数： Disqus：

问题描述

给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组（的长度）。

示例 1:

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

示例 1:

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

先上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
  int findMaxLength(vector<int>& nums) {
    unordered_map<int,int> exist;    
    int ans = 0;
    vector<int> prefix(nums.size()+1);
    for(int i=1; i<=nums.size(); ++i){
    	prefix[i] = prefix[i-1] + (nums[i-1]==0?-1:1);
    }

    for(int i=0; i<=nums.size(); ++i){
      if(exist.count(prefix[i])) ans = max(ans,i-exist[prefix[i]]);//若再次出现时，可直接计算出间隔距离，可能出现多组数据，取最大值即可
      else exist[prefix[i]] = i;   //计算前缀和第一次出现的位置
    }
    return ans;
  }
};

思路

如果把0替换为-1，若某个子数组含有相同数量的0和1，那么其和必为0。

利用前缀和是否等于0，可以在O(1)时间复杂度判断，从数组起始位置到当前位置是否含有相同数量的0和1

例如：

给定二进制数组nums：0 1 0 0 1，假定数组长度为nums

作相应的替换为：-1 1 -1 -1 1

求其前缀和

假定：vectorint prefix(n+1);存储前缀和

计算前缀和的公式：prefix[i] = prefix[i-1] + (nums[i-1]==0?1:1) //括号内为c语言三目运算符，nums[i-1]==0，则括号的值为-1,否则值为1

计算完毕，前缀和数组内容为：0 -1 0 -1 -2 -1

从前缀和可以得到两个关键信息：

  1. 若prefix[n] == 0

    表示 nums[0]+nums[1]+nums[2]+…+nums[n-1]==0，即数组nums，0到n-1具有相同的0和1

  2. 若prefix[m]==prefix[n]

    表示nums[m]+nums[m+1]+nums[m+2]+…+nums[n-1]==0

    ==我们只需求出前缀和中，值相同的两个元素间隔最长的距离即可，例如prefix[1]和prefix[5]就满足这个条件，因此该组数据的答案为5-1=4==

利用map计算值相同的两个元素间隔最长的距离

利用map记录前缀和第一次出现的位置，后续可以判断一个数是否在map里，若在里面，说明出现了值相同的两个元素，直接计算其间隔距离即可。可能存在多组数据，取最大值即可。