16 最接近的三数之和

image.png

解题思路

暴力解法 O

排序 + 双指针 O

image.png

  1. int threeSumClosest(vector<int>& nums, int target) {
  2.     sort(nums.begin(), nums.end());
  3.     int res = nums[0] + nums[1] + nums[2];
  4.     for(int i = 0; i < nums.size(); ++i){
  5.         int j = i + 1;
  6.         int k = nums.size() - 1;
  7.         while(j < k){
  8.             if(abs(res - target) > abs(nums[i] + nums[j] + nums[k] - target)) 
  9.                 res = nums[i] + nums[j] + nums[k];
  10.             if(target - nums[i] > nums[j] + nums[k])
  11.                 ++j;
  12.             else
  13.                 --k;
  14.         }
  15.     }
  16.     return res;
  17. }