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).

Solution：JAVA

public class Solution {
    public int threeSumClosest(int[] num, int target) {
        int min = Integer.MAX_VALUE;
        int result = 0;
 
        Arrays.sort(num);
 
        for (int i = 0; i < num.length; i++) {
            int j = i + 1;
            int k = num.length - 1;
            while (j < k) {
                int sum = num[i] + num[j] + num[k];
                int diff = Math.abs(sum - target);
                if (diff < min) {
                    min = diff;
                    result = sum;
                }
                if (sum <= target) {
                    j++;
                } else {
                    k--;
                }
            }
        }
 
        return result;
    }
}

C++

class Solution {
public:
    int threeSumClosest(vector<int> &num, int target) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(num.empty()) return 0;
        
        sort(num.begin(), num.end());
        int min= INT_MAX;
        int record;
        
        for(int i=0; i<num.size(); i++)
        {
            int tmp = target - num[i];
            int start = i+1, end = num.size()-1;
            while(start<end)
            {
                int sum = num[start]+num[end]+num[i];
                if(sum==target)
                {
                    min = 0;
                    record = sum;
                    break;
                }
                else if(sum > target)
                {
                    if(abs(target-sum)<min)
                    {
                    min = abs(target-sum);
                    record = sum;
                     }
                    end--;
                }
                else if(sum < target)
                {
                    if(abs(target-sum)<min)
                    {
                    min = abs(target-sum);
                    record = sum;
                     }
                    start++;
                }
            while(i<num.size()-1&&num[i]==num[i+1]) i++;
            }
        }
        return record；
    }
};

对数组求最大值，联想预处理排序