卖萌的弱渣

I am stupid, I am hungry.

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.

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

  • 3 level loops
  • 内2层循环根据sum和target的关系移动
(3Sum-Closet.py) download
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

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        ret = 0
        diff = sys.maxint
        nums = sorted(nums)
        for i in range(len(nums)):
            j = i+1
            k = len(nums)-1
            while j < k:
                sum = nums[i]+nums[j]+nums[k]
                if abs(sum-target) < diff:
                    ret = sum
                    diff = abs(sum-target)
                if sum == target:
                    return ret
                elif sum>target:
                    k = k-1
                else:
                    j = j+1
        return ret