Leetcode(16) 3Sum Closest

发表于 | 更新于 | 分类于

Description:

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

解法：

同三数和的解法，用三个指针移动遍历各种可能性。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort();
        i = 0;
        dis = 233333333;
        while(i < len(nums) - 2):
            p = i + 1;
            q = len(nums) - 1;
            remain = target - nums[i];
            while(p<q):
                if(abs(remain - nums[p] - nums[q]) < dis):
                    dis = abs(remain - nums[p] - nums[q]);
                    result = nums[i] + nums[p] + nums[q];
                if(nums[p] + nums[q] == remain):
                    return target;
                elif(nums[p] + nums[q] < remain):
                    p+=1;
                else:
                    q-=1;
            i+=1;
        return result;