LeetCode 217: Contains Duplicate Java解法超时问题求助

你的代码逻辑本身是正确的，但时间复杂度不符合题目对大数据量的要求，导致无法通过大测试用例：

• 核心问题出在ArrayList的contains()方法：它会逐个遍历列表中的元素进行匹配，每次调用的时间复杂度是O(n)
• 外层循环遍历整个数组也是O(n)，所以整体时间复杂度是O(n²)。当测试用例的数组规模很大（比如包含十万甚至百万级元素）时，总运算量会达到亿级甚至更高，直接触发时间限制超时

优化方案：使用HashSet降低时间复杂度 #

HashSet基于哈希表实现，它的contains()和add()方法平均时间复杂度都是O(1)，用它替代ArrayList后，整体时间复杂度降到O(n)，可以轻松通过所有测试用例：

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            if (numSet.contains(num)) {
                return true;
            }
            numSet.add(num);
        }
        return false;
    }
}

其他可选思路 #

你也可以先对数组排序，再遍历检查相邻元素是否重复：

• 排序的时间复杂度是O(nlogn)，遍历是O(n)，整体时间复杂度O(nlogn)，虽然比HashSet的平均情况稍差，但也是可行的方案：

import java.util.Arrays;

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i-1]) {
                return true;
            }
        }
        return false;
    }
}

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