Same idea with 3sum. 13ms


  • 0
    J
    class Solution {
    public:
        int threeSumClosest(vector<int>& nums, int target) {
            int ret = 0, dist = INT_MAX;
            if(nums.size() < 3)
                return ret;
            int len = nums.size();
            sort(nums.begin(), nums.end());
            for(int i = 0; i < len; i++){
    			int tgt = target - nums[i], front = i + 1, back = len - 1;
    			while (front < back) {
                    int sum = nums[front] + nums[back];
                    if (sum < tgt){
                        if(tgt-sum <= dist){
                            dist = tgt-sum;
                            ret = nums[i] + nums[front] + nums[back];
                        }
                        front++;
                    }
                    else if (sum > tgt){
                        if(sum - tgt <= dist){
                            dist = sum-tgt;
                            ret = nums[i] + nums[front] + nums[back];
                        }
                        back--;
                    }
                    else
                        return target;
                }
                while (i + 1 < len && nums[i + 1] == nums[i]) i++;
            }
            return ret;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.