本文共 853 字，大约阅读时间需要 2 分钟。

最长不重复连续子序列问题

双指针算法是一种优化方法，可以将暴力枚举的时间复杂度从O(n²)降低到O(n)。这种方法的核心思想是通过巧妙地利用题目特定的逻辑关系来减少计算量。

以下是双指针算法的通用模板：

for(int i=0, j=0; i < n; i++) {    while(j < n && a[j] == a[i]) {        j++;    }    int len = i - j + 1;    if(len > max_len) {        max_len = len;    }}

在这个算法中，i指针用于遍历数组中的每一个元素，j指针用于跟踪当前窗口的起始位置。当遇到重复的元素时，j指针会向前移动，确保窗口内的元素都是唯一的。这样，每个元素最多只会被访问一次，从而将时间复杂度降低到O(n)。

以下是具体实现代码：

#include 
   
    using namespace std;const int N = 100010;int n;int a[N], s[N];int main() {    cin >> n;    for(int i=0; i < n; i++) {        cin >> a[i];    }    int res = 0;    for(int i=0, j=0; i < n; i++) {        while(j < n && a[j] == a[i]) {            j++;        }        int len = i - j + 1;        if(len > res) {            res = len;        }    }    printf("%d", res);    return 0;}
   

这个代码通过维护一个滑动窗口，确保窗口内的元素都是唯一的，从而高效地解决了最长不重复连续子序列问题。这种方法不仅时间复杂度优异，还非常容易理解和实现。

转载地址：http://ohfwz.baihongyu.com/