NC41 题解 | #最长无重复子数组#

题意分析

• 给你一个数组，需要找出这个数组里面最长的子序列的长度，要求这个子序列里面的所有的数不重复。
• 前置知识，首先，你需要了解什么是子序列？
  • 子序列是一个连续的序列，你可以理解为一个数组去掉前面和后面的一部分元素形成的。
  • 然后，你需要了解如何哈希，这里的C++给我们提供了STL，里面的map就是一个很好的用来哈希的容器。
  • 最后，你需要了解双指针，双指针是我们利用两个指针，一个left，一个right，这两个指针根据题目的要求进行移动，我们枚举左指针的起点，然后右指针尽可能往右边走，直到不满足题目的意思的时候。中途我们不断维护最大的值就行了。具体请结合下面的图解理解。

• 上面的图我们可以这样理解，就是我们左边指针始终只移动一步，右边指针多次移动直到不满足条件或者到达边界，然后我们左边指针继续移动，但是在这中途需要我们维护区间的长度的最大值。具体请看下面的思路分析

思路分析

解法一 双指针法

• 上面我们进行了一些铺垫，我们在了解双指针的用法后就很好解决这个问题了，但是注意这里我们使用unordered_map对每个数字进行哈希，记录每个数字出现的次数。具体请结合相关代码进行理解。

• 代码如下

  • 需要遍历一遍整个数组，所以时间复杂度为O(n)
  • 用了unordered_map进行了哈希，所以空间复杂度为O(n)

class Solution {
public:
    /**
     * 
     * @param arr int整型vector the array
     * @return int整型
     */
    unordered_map<int,int> mp;
    int maxLength(vector<int>& arr) {
        // write code here
        int len=arr.size();
        int ans=0;
        // 定义两个指针，我们移动右指针
        for(int l=0,r=0;l<len;l++){
            // 如果右指针没有到达边界同时满足题目的条件，那么一致循环下去
            while(l<=r&&r<len&&mp[arr[r]]==0){
                mp[arr[r]]++;
                r++;
            }
            // 因为做指针需要往前移动，所以左边那个数字的个数少1
            mp[arr[l]]--;
            // 维护最大的区间长度
            ans=max(ans,r-l);
        }
        return ans;
    }
};

解法二 双端队列

• 双端队列就是一个更加实用的队列，普通的队列我们都知道是一端进，一端出的，但是双端队***实两端都可以进出。结合下图

• 直到双端队列的这个性质之后，我们可以进行如下处理，我们用一个unordered_map标记数字出现的次数，然后如果遍历整个数组，如果发现这个数字在队列里面，然后我们不断从队首出队，直到这个数字也出队。然后当前遍历的数字在队尾进行入队操作。中途维护队列的大小的最大值。

• 代码如下

  • 需要遍历一遍整个数组，所以时间复杂度为O(n)
  • 开了一个deque和unordered_map进行处理，空间复杂度为O(n)

class Solution {
public:
    /**
     * 
     * @param arr int整型vector the array
     * @return int整型
     */
    // 返回两个数字的更大的值
    int Max(int a,int b){
        if(a>b) return a;
        return b;
    }
    int maxLength(vector<int>& arr) {
        // write code here
        deque<int> q; // 定义双端队列
        unordered_map<int,int> mp;  // 用来判断某一个数字是否在队列里面，如果在，那么就是1，否则为0
        int ans=0;
        for(auto x:arr){
            // 如果当前这个数字在队列里面，那么说明存在重复的数字，队首出队
            while(!q.empty()&&mp[x]){
                mp[q.front()]=0; // 将每个出队的数字标记为0
                q.pop_front();
            }
            // 将这个数字从队尾插入
            q.push_back(x);
            mp[x]=1; // 标记
            // 维护最大值
            ans=Max(ans,q.size());
        }
        return ans;
    }
};