最长无重复元素子数组C++代码仅过25%用例问题排查

• 你的解法错误核心原因：遇到重复元素时直接清空所有已存入的城市记录，这种操作会丢失当前重复位置之前、未和当前元素冲突的无重复连续序列，导致统计的最大长度偏小。
• 复现错误的测试用例：n=5，数组为[1,2,1,3,4]，正确最长无重复子数组是[2,1,3,4]，长度为4。你的代码遇到下标为2的1时，直接清空set，丢失了未冲突的元素2，最终统计得到的最大长度只有3，和正确结果不符。

这个问题确实是经典的「最长无重复元素子数组」问题，应该用滑动窗口（双指针） 实现：

• 维护左右两个指针表示当前无重复子数组的左右边界
• 用哈希表/数组记录每个城市最后一次出现的下标
• 遍历过程中如果当前城市已经出现过，且最后一次出现的位置在当前窗口内，就把左指针移动到该城市上一次出现位置的下一位
• 每次遍历更新当前城市的最后出现位置，同时计算当前窗口长度，更新最大值

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> cities(n);
    for(int i = 0; i < n; i++)
    {
        cin >> cities[i];
    }
    int maxLength = 0;
    int left = 0;
    unordered_map<int, int> lastPos; // 存储每个城市最后出现的下标
    for(int right = 0; right < n; right++)
    {
        // 如果当前城市在当前窗口内出现过
        if(lastPos.count(cities[right]) && lastPos[cities[right]] >= left)
        {
            left = lastPos[cities[right]] + 1;
        }
        lastPos[cities[right]] = right;
        maxLength = max(maxLength, right - left + 1);
    }
    cout << maxLength << endl;
    return 0;
}

如果要进一步优化性能，因为题目限定1 < S[i] < N，可以用长度为N的数组代替unordered_map，访问速度更快。

内容的提问来源于stack exchange，提问作者MassSpectrometer