LeetCode threeSumClosest代码超时，求优化方案及思路判断

你当前的三重循环解法逻辑正确，但时间复杂度是O(n³)，当测试用例的数组长度较大时，必然会超时。这种情况下必须更换解题思路，改用排序+双指针的方案，把时间复杂度降到O(n²)，就能通过所有测试用例。

具体优化思路 #

1. 先对数组进行排序，排序耗时O(n log n)，这一步是后续双指针操作的基础。
2. 固定第一个元素，用左右双指针分别指向剩余元素的首尾位置：
   • 计算三数之和，对比当前和与目标值的差距，更新最接近的结果。
   • 如果当前和小于目标值，左指针右移，让和变大；如果当前和大于目标值，右指针左移，让和变小。
   • 一旦出现三数之和等于目标值的情况，直接返回该结果，因为这已经是最接近的情况。

优化后的代码 #

import java.util.Arrays;

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        // 先排序数组
        Arrays.sort(nums);
        int n = nums.length;
        // 初始化最接近的和为前三个元素的和
        int closestSum = nums[0] + nums[1] + nums[2];
        
        for (int i = 0; i < n - 2; i++) {
            // 双指针初始化
            int left = i + 1;
            int right = n - 1;
            
            while (left < right) {
                int currentSum = nums[i] + nums[left] + nums[right];
                // 如果当前和更接近目标值，更新结果
                if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
                    closestSum = currentSum;
                }
                // 如果找到完全相等的情况，直接返回
                if (currentSum == target) {
                    return currentSum;
                } else if (currentSum < target) {
                    // 和太小，左指针右移
                    left++;
                } else {
                    // 和太大，右指针左移
                    right--;
                }
            }
        }
        return closestSum;
    }
}

为什么这个思路能解决超时问题 #

原来的三重循环会遍历所有可能的三元组，当数组长度是1000时，计算次数约1.6亿次，完全超出时间限制。而排序+双指针的方案，每个固定元素对应的双指针遍历是O(n)，整体计算次数是O(n²)，1000长度的数组计算次数约100万次，效率提升了两个数量级，足以通过所有测试用例。

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