连续数组

Trace

6.3 每日一题

传送门：<https://leetcode-cn.com/problems/contiguous-array/>

暴力

遍历起点终点+前缀和，时间复杂度$O(n^2)$

前缀和+哈希表

可以将数组中的0视为-1，然后可以将题意理解为找和为0的最长连续子数组。

记前缀和数组为$q[N]$，下标$i$到下标$j$的区间和为$q[j]-q[i-1]$，假如$q[i-1]$和$q[j]$的值相同，那么$(q[j]-q[i-1])$等于0，符合条件。

因此，只需要求最长的符合条件的情况，这里采用哈希表来降低时间复杂度。哈希表的$key$为前缀和，$value$为这个前缀和第一次出现的索引。

在程序中遍历一次前缀和数组，如果在哈希表中没有出现，则存入哈希表；如果出现过可以更maxn，此时不需要更新哈希表。

注意：要将前缀和为0存入前缀和的第一项。

程序

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int maxn=0;
        //前缀和
        int q[100100];
        q[0]=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]==1){
               q[i+1]=q[i]+1;
            }
            else{
               q[i+1]=q[i]-1;
            }
        }
        //哈希表
        map<int,int> mp;
        mp[0]=0;
        for(int i=1;i<=nums.size();i++){
            int tnt=q[i];
            if(mp.count(tnt)>0){
                maxn=max(maxn,i-mp[tnt]);
            }
            else{
                mp[tnt]=i;
            }
        }
        return maxn;
    }
};