LeetCode「存在重复元素」代码超时问题排查

题目背景 #

给定整数数组nums，若数组中存在至少一个重复元素则返回true，若所有元素均唯一则返回false。

提交的代码 #

bool containsDuplicate(int* nums, int numsSize) {
    int i, j;
    int k = 0;
    int f = 0;
    for (i = k + 1; i < numsSize; i++)
    {
        if (nums[k] == nums[i])
        {
            f = 1;
            break;
        }

        if (i == numsSize - 1)
        {
            k++;
            i = k;
        }
    }

    if (f == 1)
        return true;
    else 
        return false;
}   

遇到的问题 #

上述代码在LeetCode提交时出现时间超限（Time Limit Exceeded），尝试用单循环实现判断逻辑，但代码运行失败。

超时原因与代码问题分析 #

• 时间复杂度过高：这段代码本质是嵌套循环逻辑，虽然用单循环写法伪装，但实际是对每个元素nums[k]，遍历其之后的所有元素做重复比较，时间复杂度为O(n²)。当数组长度n极大时（比如LeetCode测试用例包含上万级元素），这种算法的运行时间会远超题目允许的上限，直接触发超时。
• 循环逻辑存在冗余错误：当k递增到numsSize-1时，i = k会让循环进入无意义的遍历，浪费额外运行时间；同时这种单循环嵌套的写法不仅没有简化逻辑，反而降低了代码可读性。
• 无性能优化空间：对于无重复元素的大数组，代码必须完成所有元素的两两比较，没有提前终止或剪枝的优化，这是导致超时的核心原因。

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