算法基础课题解合集

双指针算法

双指针算法指通过两个指针 $i$ 和 $j$ 去优化某些问题，比如把本题的 $O(n^2)$ 复杂度的暴力优化成 $O(n)$ 的 $AC$ 算法。

常见的双指针算法比如归并排序的合并就是两个指针扫描两个排序数组

暴力解法

双重循环枚举起点和中点，然后判断一下区间是否无重复。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
int n, a[N], s[N];

bool check(int l, int r) {
    unordered_map<int, bool> m;
    for (int i = l; i <= r; i ++) {
        if (m[a[i]]) return false;
        m[a[i]] = true;
    }
    return true;
}

int main() {
    cin >> n;
    int res = 0;
    for (int i = 0; i < n; i ++) cin >> a[i];
    for (int i = 0; i < n; i ++)
        for (int j = 0; j <= i; j ++) 
            if (check(j, i)) 
                res = max(res, i - j + 1);
    cout << res << endl;
    return 0;
}

但显然这个代码会 $T$，因为进行了太多本不可能的状态的枚举。

双指针优化思路

我们用一个 $j$ 指针扫描区间头部，$i$ 指针则是区间尾部，我们规定 $i$ 指针在前，$j$ 指针在后，而且 $[j,i]$是当前最长的无重复子序列，然后我们可以发现一些性质：

$j$ 指针只能往前走，因为如果往后走，那么就会有一个比它更长的无重复序列出现，而这和我们的定义矛盾，而 $i$ 就更不可能往前走了，如果 $i$ 往前走，那么当前的子序列一定比 $i$ 往前走后的序列大。

因此，$i$ 和 $j$ 都只能往后走。

算法步骤

准备：用一个 $S$ 数组来记录数组里每一个数出现的次数。

1. $i$ 遍历数组里所有的数。

2. 每次先把 $A_i$ 加入序列中，然后如果 $A_i$ 的出现次数大于 $1$ 的话，就一直把序列头的数踢出序列，知道 $A_i$ 只出现一次为止。

3. 更新当前最大长度。

代码

/*
    其实说了这么多思路，但代码倒是挺短的。
    双指针是典型的代码短，思维难度高的思维题。
*/
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
int n, a[N], s[N];

int main() {
    cin >> n;
    int res = 0;
    for (int i = 0; i < n; i ++) cin >> a[i];
    for (int i = 0, j = 0; i < n; i ++) {
        s[a[i]] ++;
        while (s[a[i]] > 1) s[a[j]] --, j ++;
        res = max(res, i - j + 1);
    }
    cout << res << endl;
    return 0;
}

好啦，这篇超超超超详细的题解到这里就结束啦！感谢观看！！！

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$