LeetCode 16. 最接近的三数之和

时间:2022-06-04 23:47:36

题意

从给定的数组中选出三个数,使得三个数的和最接近目标值。

思路

  • 想法1:暴力,(O(n^3))
  • 想法2:排序 双指针。上题中的想法可直接拿过来用,改一下返回的结果就可以了。时间复杂度:(O(n^2)),空间复杂度:(O(n))

代码

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {

        int len = nums.size();
        sort(nums.begin(), nums.end());

        int L, R;
        int res = nums[0]   nums[1]   nums[2];
        for(int i = 0; i < len;   i)
        {
            L = i   1;
            R = len - 1;
            while(L < R)
            {
                int sum = nums[i]   nums[L]   nums[R];
                if(sum == target)   return target;

                if(abs(sum - target) < abs(res - target))   res = sum;

                if(sum > target)
                    --R;
                else
                      L;
            }
        }
        return res;
    }
};

总结

排序 指针。