Leetcode_C++之525. Contiguous Array（连续子数组）

题目名称

Contiguous Array

题目描述

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

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

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

Constraints:
1 <= nums.length <= 10e5
nums[i] is either 0 or 1.

初试思路

见注释和视频b站

初试代码

// 我的代码
class Solution {
public:
    int findMaxLength(vector& nums) {
        // 遍历从下标i到下标j的子串中符合条件的最长的子串，返回其长度
        // 即count0[i to j] == count1[i to j] 
        // => count0[0 to j] - count0[0 to i] == count1[0 to j] - count1[0 to i]
        // => count0[0 to j] - count1[0 to j] == count0[0 to i] - count1[0 to i]
        // => diffcount[j] == diffcount[i]
        // 遍历找到符合条件的最大的 i to j的长度

        int MaxLen = 0; //最大子串长度
        int MaxJ = 0;   //最大的j的值
        // diffcount数组存放nums中从下标0到每个下标的“0的个数与1的个数差”，其长度为nums.size()+1，原因见初始化
        vector diffcount(nums.size()+1); // -1 0 1 2 ... nums.size()-1
        diffcount[dindex(-1)] = 0; //下标0之前的下标“-1”对应的元素置零0
        // 初始化diffcount数组, 如果nums[i]==0，则将diffcount[dindex(i)]的值置为前一个元素+1
        //                      如果nums[i]==1，则将diffcount[dindex(i)]的值置为前一个元素-1
        for(int i=0; i maxj(nums.size()*2+1); // -nums.size ... 0 ... nums.size()
        for(int i=-nums.size(); i MaxLen) //if(MaxJ-i+1 > MaxLen) //会使得Maxlen = 1而这明显是错的
                MaxLen = MaxJ-i+1;    
        }
        return MaxLen;   
    }

    int dindex(int i){
        return i+1;
    }
    int mindex(int i, int size){
        return i+size;
    }

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

推荐思路

1、一个数组即可，存放当前0的个数和1的个数的差
2、因为数组是稀疏的，好多用不到，所以可以用哈希表

推荐代码

// 别人的代码1
class Solution {
public:
    int findMaxLength(vector& nums) {
		vector arr(2*nums.size() + 1, INT_MIN);
		arr[nums.size()] = -1;
        int maxLen = 0, sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += (nums[i] == 0 ? -1 : 1);
			if (arr[sum + nums.size()] >= -1)  maxLen = max(maxLen, i - arr[sum + nums.size()]);
			else  arr[sum + nums.size()] = i; 
        }
        return maxLen;
    }
};
//别人的代码2
class Solution {
public:
    int findMaxLength(vector& nums) {
        int sum=0, maxLen=0;
        unordered_map seen{{0, -1}};
        
        for(int i=0; i