解法

  • 暴力解法：三趟遍历，时间复杂度为n3

  • 双指针法：令一个值为具体值，其他两个值为指针值，先排序，如果计算的结果大于target，那么就让right–，否则就left++

    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
    #include <algorithm>
    #include <climits>
    #include <cstdlib>
    class Solution {
    public:
      int threeSumClosest(vector<int> &nums, int target) {
        std::sort(nums.begin(), nums.end());
        if (nums.size() < 3) {
          return 0;
        }
        int x = nums[0] + nums[1] + nums[2];
        int diff = x - target;
        for (int i = 0; i < nums.size(); i++) {
          int j = i +1;
          int k = nums.size() - 1;
          while (j < k) {
            x = nums[i] + nums[j] + nums[k];
            if (abs(x - target) < abs(diff)) {
              diff = x - target;
            }
            if (x < target) {
              j++;
            } else {
              k--;
            }
          }
        }
        return diff + target;
      }
    };

  • 双指针法的优化：如果结果和target相同时，即可先返回，可降低一定的时间复杂度

    1
    2
    3
    if (target == x) {
        return diff + target;
    }

思考

涉及到三个数的结果时，可以考虑使用三次遍历，但是这样得时间复杂度过高。

所以可以考虑减少一层循环，降低为一个数和两个数的结果，使用双指针，在排序后的结果中进行选择。先确定一个数，即一层for循环，再用双指针查找确定另外两个数。

那么，双指针移动的规则是什么？

让三个数相加，如果结果比target小，那么就让left++，找到更接近的，反之right–，也可以找到最近的，注意在这个过程中保存中间结果。