首页 > 代码库 > LeetCode:3Sum Closest

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;    }};

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

LeetCode:3Sum Closest