今天的题目是三数相加两件套

分别是

  • 三数之和

  • 最接近的三数之和

以下是题解

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
class Solution {
public:
  vector<vector<int>> threeSum(vector<int> &nums) {
    if (nums.size() < 3)
      return {};
    if (nums.size() == 3 && !(nums[0] + nums[1] + nums[2]))
      return {nums};
    sort(nums.begin(), nums.end());
    vector<vector<int>> res{};
    for (auto i = 0; i < nums.size(); ++i) {
      auto req{nums[i]};
      if (req > 0) break;
      if (i > 0 && req == nums[i - 1])
        continue;
      auto l{i + 1};
      auto r{nums.size() - 1};
      while (l < r) {
        auto left{nums[l]}, right{nums[r]};
        auto sum{left + right + req};
        if (!sum) {
          res.push_back({req, left, right});
          // 跳过一样的项, 确保返回的三元组不重复
          do ++l;
          while (l < r && nums[l] == left);
          do --r;
          while (l < r && nums[r] == right);
        } else if (sum < 0)
          ++l;
        else
          --r;
      }
    }
    return res;
  }

  int threeSumClosest(vector<int> &nums, int target) {
    sort(nums.begin(), nums.end());
    // 2, 3, 8, 9, 10    16
    auto max{nums.size() - 1};
    auto diff{numeric_limits<int>::max()};
    auto res{diff};
    for (auto i = 0; i < nums.size() - 2; ++i) {
      auto req{nums[i]};
      // 如果当前数字和上一个一样跳过
      if (i > 0 && req == nums[i - 1])
        continue;
      // 检查可能的最大值
      auto cur_max{req + nums[max] + nums[max - 1]};
      if (cur_max < target) {
        auto cur_diff{target - cur_max};
        if (cur_diff < diff) {
          diff = target - cur_max;
          res = cur_max;
        }
        continue;
      }
      // 检查可能的最小值
      auto cur_min{req + nums[i + 1] + nums[i + 2]};
      if (cur_min > target) {
        auto cur_diff{cur_min - target};
        if (cur_diff < diff) {
          res = cur_min;
        }
        break;
      }
      // 常规逼近查找
      auto l{i + 1};
      auto r{max};
      while (l < r) {
        auto left{nums[l]}, right{nums[r]};
        auto sum{left + right + req};
        if (sum == target) {
          return sum;
        }
        if (sum < target) {
          auto cur_diff{target - sum};
          if (cur_diff < diff) {
            diff = cur_diff;
            res = sum;
          }
          ++l;
        }
        if (sum > target) {
          auto cur_diff{sum - target};
          if (cur_diff < diff) {
            diff = cur_diff;
            res = sum;
          }
          --r;
        }
      }
    }
    return res;
  }
};

主要思路就是有序序列下的逼近查找方案