Saturday, November 15, 2014

[LeetCode] 3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).



思路:

3sum问题的变种。一样的遍历每个数,对剩余数组进行双指针扫描。区别仅仅在于当:
sum = A[left] + A[right]
(1) sum = target时直接返回
(2) sum != target时,在相应移动left/right指针之前,先计算abs(sum-target)的值,并更新结果。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int threeSumClosest(vector<int> &num, int target) {
        if(num.size()<3) return INT_MAX;
        sort(num.begin(),num.end());
        int minDiff = INT_MAX;
        for(int i=0; i<num.size()-2; i++) {
            int left=i+1, right = num.size()-1;
            while(left<right) {
                int diff = num[i]+num[left]+num[right]-target;
                if(abs(diff)<abs(minDiff)) minDiff = diff;
                if(diff==0) 
                    break;
                else if(diff<0)
                    left++;
                else
                    right--;
            }
        } 
        return target+minDiff;
    }
};

No comments:

Post a Comment