AcWing 799. 画个简图辅助理解

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 799. 画个简图辅助理解原题链接简单

作者：

liangshang , 2020-05-21 23:04:07 , 所有人可见 , 阅读 15148

209

122

C++ 代码

#include <iostream>
using namespace std;

const int N = 100010;
int a[N], count[N];
int n, ans;

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 0, j = 0; j < n; j++) {
        count[a[j]] ++;
        while (count[a[j]] > 1) {
            count[a[i]] --;
            i++;
        }
        ans = max(ans, j - i + 1);
    }
    printf("%d", ans);
    return 0;
}

时间复杂度：使用双指针的题目一般都是$O(n)$
空间复杂度：标记数组占内存比较大，数组长度为数据范围上界，其实完全可以用哈希表代替，这样优化后额外的空间复杂度就是$O(n)$

55 评论

Shier833_Ww 2023-02-02 12:01

感谢图解！很清晰！分享个人看了楼主图解后，对while循环的理解：

        while (count[a[j]] > 1) {
            //分析点①(while循环逻辑)：发现j指向的数前面出现重复的之后，j停止；i开始向j靠近，靠近过程中得把i前面的标记位从1置0;
            //直到i找到了和j重复的那个数后，count[a[i]] --也就使得count[a[j]]置0,＜1就退出while循环了
            count[a[i]] --;//分析点②：要先--，再i++,否则就落掉当前i指向的那个数对应的标志位置0，还会导致while循环提前退出
            i++;
        }

Pobz 2023-01-06 11:22

xyd 2023-03-27 16:24

图来

RNM 10个月前回复了 xyd 的评论

脑婆脑婆

嘤雄达拉崩吧 2022-08-18 09:49

你们的那个图都是哪里画的啊？

奔马 2022-09-07 14:32

同问

国乙私人bot 2023-01-19 16:05

同问

宝藏男孩青蛙王子 2023-04-06 14:51

平板

椎名真由理 2023-05-22 09:12

感觉像vision

xuekai 2022-03-06 10:52

个人理解：
为方便表述，记最长连续不重复子序列为C，
[i, j]表示当前C，长度是j - 1 + 1。
j指针用于遍历数组a，当发生重复，一定是a[j]与前面的a[k]相等，其中i <= k <= j - 1。
若发生重复，用i指针来清除[i, k]范围内的数组a的值在数组count中的标记，确保数组count只记录[i, j]即当前C中出现的数字。
由于无从得知这个C的起始下标和结束下标，因此每轮循环对ans的值与当前C的长度j - 1 + 1取max。