LeetCode

LeetCode-16 最接近的三数之和

nkul · 9月27日 · 2020年 · 40次已读

LeetCode-15 三数之和

2020-9-27 0

本题比上题更简单,不用去重。进行到“找到最接近且大于等于target的k时”,此时i,j,k大于target,i,j,k-1小于target,比较且更新即可!

class Solution {
public:
    int threeSumClosest(vector& nums, int target) {
        sort(nums.begin(),nums.end());
        // first:与target的差值,second:和
        pair res(INT_MAX,INT_MAX);
        for(int i = 0;i < nums.size(); i++){
            for(int j = i+1 ,k = nums.size() - 1 ; j < k ;j ++ ){
                //此时的k是 满足最接近且大于target的k,并且,k-1满足最接近且小于target
                while(k - 1 > j && nums[i] + nums[j] + nums[k - 1] >= target) k--;
                int s = nums[i] + nums[j] + nums[k];
                res = min(res , make_pair(abs(s - target), s));
                if(k - 1 > j){
                    s = nums[i] + nums[j] + nums[k - 1];
                    res = min(res , make_pair(target - s, s));
                }
            }
        }
        return res.second;
    }
};
template inline
	bool operator<(const pair<_Ty1, _Ty2>& _Left,
		const pair<_Ty1, _Ty2>& _Right)
	{	// test if _Left < _Right for pairs
	return (_Left.first < _Right.first ||
		!(_Right.first < _Left.first) && _Left.second < _Right.second);
	}

简而言之就是先比较first,相等再比较second。



0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!