如何优化LeetCode中ThreeSum的解决方案？解决超时问题

超时核心原因 #

你代码里的ans.contains(temp)是导致超时的关键——这个方法会遍历整个结果集做线性匹配，时间复杂度是O(m)（m为当前结果集大小）。面对超大测试用例时，整体时间复杂度会飙升到O(n²*m)，直接触发TLE。

优化思路（利用数组已排序的特性） #

既然已经对数组做了排序，完全可以通过跳过重复元素来避免结果集重复，根本不需要用contains做判断：

• 外层循环：如果当前基准元素nums[i]和前一个元素nums[i-1]相等，直接跳过，避免生成重复的三元组。
• 找到和为0的三元组后：
  • 左指针持续右移，直到遇到和当前左值不同的元素，跳过重复左值。
  • 右指针持续左移，直到遇到和当前右值不同的元素，跳过重复右值。
• 额外优化：如果基准元素nums[i] > 0，直接终止外层循环——排序后后面的元素都是正数，三个正数相加不可能为0。

优化后的代码示例 #

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums); 
        List<List<Integer>> ans = new ArrayList<>(); 
        int left, right, sum;
        for(int i = 0; i < nums.length; i++){
            // 基准元素大于0，直接结束循环
            if(nums[i] > 0) break;
            // 跳过重复的基准元素
            if(i > 0 && nums[i] == nums[i-1]) continue;
            
            left = i + 1; 
            right = nums.length - 1;
            while(left < right){
                sum = nums[i] + nums[left] + nums[right]; 
                if(sum == 0){
                    ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 跳过左指针重复值
                    while(left < right && nums[left] == nums[left+1]) left++;
                    // 跳过右指针重复值
                    while(left < right && nums[right] == nums[right-1]) right--;
                    // 移动指针寻找下一组
                    left++;
                    right--;
                }else if(sum < 0){
                    left++; 
                }else{
                    right--; 
                }
            }
        }
        return ans; 
    }
}

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