算法日记3：星码P36最长连续不重复子序列（双指针）

贴个链接嘿嘿：https://www.starrycoding.com/problem/36

一、题面

二、解题思路：

• 对于这个题目有一个误区，就是不一定不符合题意的内容一定连续的。

4
1 2 3 2

• 例如：这个样例，就会使得让序列不符合条件的数字不连续（即2不连续）

2.1：法一、暴力解决方法：(0(n⁴))

• 1、对于这个问题，我们最直观的想法就是两层for循环遍历，对于每次遍历，都调用一个check函数来检查是否合法
  
• 2、比如：在这个数组中，我们需要遍历它的所有的子序列，一旦发现其中有重复元素，那么就说明不合法，直接return fasle
• 3、假如我们遍历结束之后都没有进入这个if语句，那么就说明这个序列是合法的，return true
  

2.2法二、双指针优化 (0(n))

• 1、因为题目的样例达到了1e5所以我们可以考虑使用双指针优化
• 2、我们考虑开一个数组int st[N];来表示某个数字出现的次数，（ i 表示遍历到了哪个数字， j 表示合法区间的左边界）
  

st[1]++

st[2]++

st[2]++

• 3、此时，st[2]=2>1也就说明了此时，已经访问到了一个不合法区间，
• 我们要进行操作，把 j 移动到合法位置(这个位置不一定是i) 比如这个样例

4
1 2 3 2

• 并且将之前的区间全部抛弃掉，也就是要从合法区间重新开始计算st[i]的值！
• 要达成这个目标，我们可以这样
  

 while(st[a[i]]>1) //表明这个数字已经访问过了,此时已经不合理
        {
            st[a[j]]--;
            j++;
        }

• 4、随后只要符合条件，我们就计算i-j+1来计算合法长度，我们就成功解决了这个问题，代码如下：

for(int i=1,j=1;i<=n;i++)
    {
        st[a[i]]++; //次数加1
// 当出现重复元素时，移动 j 缩小窗口
        while(st[a[i]]>1) //表明这个数字已经访问过了,此时已经不合理
        {
            st[a[j]]--;
            j++;
        }
        // 每次更新最长子数组长度
        MAX_N=max(MAX_N,i-j+1);
    }

三、完整代码参考

注意多个样例时要重置数组😂

#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 7;
int a[N];
int st[N];

void solve() {
    memset(a, 0, sizeof(a));
    memset(st, 0, sizeof(st));
    
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    int MAX_N = 0;
   for(int i=1,j=1;i<=n;i++)
    {
        st[a[i]]++; //次数加1
// 当出现重复元素时，移动 j 缩小窗口
        while(st[a[i]]>1) //表明这个数字已经访问过了,此时已经不合理
        {
            st[a[j]]--;
            j++;
        }
        // 每次更新最长子数组长度
        MAX_N=max(MAX_N,i-j+1);
    }
    
    cout << MAX_N << '\n';
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1; 
    cin >> _;
    while (_--) solve();
    return 0;
}

原文地址：https://blog.csdn.net/2301_79365218/article/details/145161955

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！