首页 > 其他 > 详细

3Sum Closest

时间:2017-03-11 23:49:27      阅读:272      评论:0      收藏:0      [点我收藏+]

思路:先对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

原文:http://www.cnblogs.com/chengyuz/p/6536548.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!