文章详情

AcWing 799. 最长连续不重复子序列

作者：

linzy 浏览：169 2021年3月22日 21:36

### AcWing 799. 最长连续不重复子序列

#### 题目链接：

[AcWing 799. 最长连续不重复子序列](https://www.acwing.com/problem/content/801/)

[LeetCode 3. 无重复字符的最长子串](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/)

#### 题目思路：双指针

双指针的应用很多时候都是对暴力算法的优化，如：

双重循环需要o(n2)的时间复杂度，通过寻找题目中的性质（如单调性）可以使用双指针法对其进行优化，从而达到o(n)的时间复杂度。

所以能用双指针的地方基本上都可以使用暴力做法，如果暴力做法不超时的话也就不用特地使用双指针算法了。那么为了更清楚的得出双指针的推导过程，先说明一下暴力做法从而得出双指针算法。

##### 暴力算法：

时间复杂度O(n2)

使用两重循环，第一重循环遍历子序列的开头，第二重循环比那里子序列的结尾

```c++
for(int i = 0; i < n; i ++) // 遍历以每个点为开头的子序列
{
    for(int j = i; j < n; j++)
    {
        if(check(j))j++; // 判断当前j的元素是否在子序列里面是否有重复，如果没有则继续
        else{//重复则求出当前子序列长度，并推出
            res = max(res,j - i + 1);
            break;
        }
    }
}
```

##### 双指针算法：

时间复杂度O(n)

**分析一下暴力算法中重复的计算：**

使用i，j表示子序列的头尾指针，进行维护子序列。

例如：[1,2,3,4,5,4,6]

那么当头指针指向1的时候尾指针最多可以直到5，到6之后就会有重复（重复数字为4）。所以在从[1,6]的范围内可以得出最长的不重复子序列为res = 5.

可发现重复数字是4，所以如果i的位置还在4之前，那么j的位置是永远不会高于6，那么不重复子序列的长度也不可能超过之前的5。所以当i在遍历在4之前j所有的遍历循环都是重复的，是可以剪枝掉的。

**暴力算法重复计算过程：**

![最长不重复子序列2](https://images.21hut.com/typora/202103/16/191519-569528.gif)

**一重循环优化：双指针**

双指针做法的思想是可以通过题目的一些性质，将两层循环的两个指针，缩减为一层循环两个指针。

题目的性质：

1. 当头指针往前走后，假如出现了重复的数字，而之前是没有的，可以得出新进子序列的这个数就是那个重复的数字

那我们可以发现，每次j走前面之后就不用再往回走重新遍历了，所以是可以省去第二重循环的。

**双指针解题过程：**

![最长不重复子序列](https://images.21hut.com/typora/202103/16/191521-380476.gif)

#### 代码：

``` c++
#include<iostream>
using namespace std;
const int N = 1e5+10;
int p[N],a[N];
int main()
{
    int n;
    cin>>n;
    
    for(int i = 0; i < n; i ++)cin>>p[i];
    int res = 0;
    for(int i = 0, j = 0; i < n; i ++)
    {
        // 将新进入序列的数+1
        a[p[i]] ++;
        // 如果i往前走了一位之后发现该序列里面出现了重复的数字，那么j往后走，直到当前序列里面没有重复数字
        while(a[p[i]] > 1)a[p[j++]]--;
        res = max(res , i - j + 1);
    }
    cout << res << endl;
    return 0;
}
```

#### 总结：

双指针的应用是对双重循环的暴力算法的一种优化。

而能否使用双指针进行优化，就的看题目有没有满足双指针的性质。稍微总结一下

满足双指针的性质：当一个指针发生改变的时候，另一个指针可以不用重复遍历他已经遍历过的数就能够证明这样的正确性。

如该题中所示：当头指针碰到重复数字的时候，修改尾指针在尾指针碰到前重复数字之前，他位置的改变，头指针是不用重复遍历其之前遍历过的数来证明头指针改变的正确性。

这样就只要走一遍循环就可以解决问题了。而发现这个性质就是使用双指针的关键。

AcWing 799. 最长连续不重复子序列

请登录后回复

共有0条评论