16. 3Sum Closest

题目

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

1
2
3
Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

题目大意

给定一个数组，要求在这个数组中找出 3 个数之和离 target 最近。

解题思路

  1. 初始值优化：
    • 原代码中it初始化为 0，在某些特殊情况下（如所有可能的和都是正数且较大）可能导致额外计算
    • 改为使用数组前三个元素的和作为初始值，更合理地设置了起点
  2. 重复元素跳过：
    • 对第一个元素i：当nums[i] == nums[i-1]时直接跳过，避免处理相同的第一个元素
    • 对双指针j和k：使用do-while循环跳过重复值，减少无效比较
  3. 早期终止策略：
    • 对每个i计算最小可能和（nums[i] + nums[j] + nums[j+1]），如果这已经大于target，后续i更大，和只会更大，可直接退出外层循环
    • 计算最大可能和（nums[i] + nums[k-1] + nums[k]），如果这已经小于target，可记录后直接尝试下一个i
  4. 计算效率提升：
    • 减少绝对值计算次数，一次计算后多次使用
    • 通过早期终止避免了大量不必要的循环迭代
    • 紧凑的指针移动逻辑减少了条件判断次数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        
        // 初始化it为前三个元素的和，避免初始值为0的潜在问题
        int it = nums[0] + nums[1] + nums[2];
        int diff = abs(it - target);
        
        for (int i = 0; i < n - 2; ++i) {
            // 跳过重复的第一个元素，减少无效计算
            if (i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            
            int j = i + 1;
            int k = n - 1;
            
            // 早期终止优化：当前i的最小可能和
            int min_sum = nums[i] + nums[j] + nums[j+1];
            if (min_sum > target) {
                int current_diff = min_sum - target;
                if (current_diff < diff) {
                    it = min_sum;
                    diff = current_diff;
                }
                break;  // 后续i更大，和只会更大，无需继续
            }
            
            // 早期终止优化：当前i的最大可能和
            int max_sum = nums[i] + nums[k-1] + nums[k];
            if (max_sum < target) {
                int current_diff = target - max_sum;
                if (current_diff < diff) {
                    it = max_sum;
                    diff = current_diff;
                }
                continue;  // 尝试下一个更大的i
            }
            
            // 双指针查找
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                int current_diff = abs(sum - target);
                
                // 找到完美匹配，直接返回
                if (current_diff == 0) {
                    return sum;
                }
                
                // 更新最接近的和
                if (current_diff < diff) {
                    it = sum;
                    diff = current_diff;
                }
                
                // 移动指针
                if (sum < target) {
                    // 跳过重复的j值
                    do { j++; } while (j < k && nums[j] == nums[j-1]);
                } else {
                    // 跳过重复的k值
                    do { k--; } while (j < k && nums[k] == nums[k+1]);
                }
            }
        }
        
        return it;
    }
};