【双指针】最长连续不重复子序列
我真的是个脑瘫。 原题连接:https://www.acwing.com/problem/content/description/801/
维护j到i的不包含重复的数的区间和区间长度的最大值。每次新加进i之后,如果不合理,则前进j,直到合理为止。前进j的时候记得更新s的状态。
/*
核心思路:
遍历数组a中的每一个元素a[i], 对于每一个i,找到j使得双指针[j, i]维护的
是以a[i]结尾的最长连续不重复子序列,长度为i - j + 1, 将这一长度与r的
较大者更新给r。
对于每一个i,如何确定j的位置:由于[j, i - 1]是前一步得到的最长连续不
重复子序列,所以如果[j, i]中有重复元素,一定是a[i],因此右移j直到a[i]
不重复为止(由于[j, i - 1]已经是前一步的最优解,此时j只可能右移以剔除
重复元素a[i],不可
共有 0 条评论