LeetCode之16. 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).

题目大意：

给定一个n个整数的数组S，找出其中三个元素的和sum最接近目标target数，并返回和sum。

算法解析：

先循环遍历前n-2个元素，然后第二个元素（i+1）和第三个元素采用比较大小的方式按位增减。同时比较第i个、第i+1和length-1个元素的和sum与目标数target的大小，返回最接近目标数的sum。

代码如下：

• Java

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int length = nums.length;
        int min = Integer.MAX_VALUE;
        Arrays.sort(nums);
        for (int i=0; i<length-2; i++) {
            int begin = i+1;
            int end = length-1;
            if (i>0 && nums[i] == nums[i-1])
                continue;
            while (begin < end) {
                int sum = nums[i] + nums[begin] + nums[end];
                if (Math.abs(sum - target) < Math.abs(min))
                    min = sum-target;
                else if (sum == target)
                    return target;
                else if (sum < target)
                    begin++;
                else
                    end--;
            }
        }
        return min+target;
    }
}

• Python

class Solution:
    # @param {integer[]} nums
    # @param {integer} target
    # @param {integer}
    def threeSumClosest(self, nums, target):
        length = len(nums)
        min = 2147483647
        nums.sort()
        for i in range(length-2):
            if i>0 and nums[i] == nums[i-1]:
                continue
            begin = i+1;end=length-1
            while begin<end:
                sum = nums[i]+nums[begin]+nums[end]
                if abs(sum-target)<abs(min):
                    min = sum-target
                if sum==target:
                    return target
                elif sum<target:
                    begin+=1
                else:
                    end-=1
        return min+target