C++求解数组最长连续序列长度代码返回错误结果排查求助

问题原因 #

• 核心错误：使用unordered_map的[]运算符获取arr[i]-1和arr[i]+1的长度时，如果对应key不存在，会自动将该key插入哈希表并赋值为默认值0。这就导致后续遍历到这些key对应的数组元素时，mp.count(arr[i])会返回true，直接跳过处理逻辑，绝大多数元素没有被正常计算，所以最终返回结果为1。
• 次要问题：没有将当前处理的arr[i]显式存入哈希表，即使修复第一个问题，后续遇到重复元素时也无法被正确去重，相邻元素查询也可能拿不到正确值。

修复后的代码 #

int findLongestConseqSubseq(int arr[], int N)
{
    unordered_map<int,int> mp;
    int ans = 0;
    for(int i=0; i<N; i++){
        // 重复元素直接跳过
        if(mp.count(arr[i]) > 0){
            continue;
        }
        // 用find查询避免插入多余key
        int len1 = 0;
        if(mp.find(arr[i]-1) != mp.end()){
            len1 = mp[arr[i]-1];
        }
        int len2 = 0;
        if(mp.find(arr[i]+1) != mp.end()){
            len2 = mp[arr[i]+1];
        }
        int ns = len1 + len2 + 1;
        ans = max(ans, ns);
        // 更新序列两端的长度
        mp[arr[i] - len1] = ns;
        mp[arr[i] + len2] = ns;
        // 将当前元素存入哈希表避免重复处理
        mp[arr[i]] = ns;
    }
    return ans;
}

修复说明 #

• 将[]运算符直接取值改为先通过find判断key是否存在，不存在则长度为0，避免插入多余的key。
• 处理完当前元素后显式将arr[i]存入哈希表，保证重复元素可以被正确跳过。

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