首页 > 代码库 > 3Sum Closest

3Sum Closest

2024-09-08 05:11:26   213人阅读

思路：先对vector进行排序，然后夹逼计算，时间复杂度O(n^2)，里面需要注意在判断完边界后，先计算thres和result，然后处理下标，这里不需要考虑重复情况。

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        
        int sum = 0;
        int thres = INT_MAX;
        int result = nums[0] + nums[1] + nums[2];
        for(int i=0; i<nums.size()-2; ++i)
        {
            int j = i+1;
            int k = nums.size() - 1;
            
            while(j<k)
            {
                if(nums[i] + nums[j] + nums[k] < target)
                {
                    if(fabs(nums[i] + nums[j] + nums[k] - target) < thres)
                    {
                        thres = fabs(nums[i] + nums[j] + nums[k] - target);
                        result = nums[i] + nums[j] + nums[k];
                    }
                    ++j;
                }
                else if(nums[i] + nums[j] + nums[k] > target)
                {
                    if(fabs(nums[i] + nums[j] + nums[k] - target) < thres)
                    {
                        thres = fabs(nums[i] + nums[j] + nums[k] - target);
                        result = nums[i] + nums[j] + nums[k];
                    }
                    --k;
                }
                else
                {
                    return nums[i] + nums[j] + nums[k];
                }
            }
        }
        return result;
    }
};

 

3Sum Closest


联系
我们