卖萌的弱渣

I am stupid, I am hungry.

Three Sum Closest

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.

Example

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

Note

You may assume that each input would have exactly one solution.

Challenge

O(n2) time, O(1) extra space

Solution

  • Time: O(N2), Space O(1)
  • Idea is similar to Three Sum
(Three-Sum-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
26
27
28
29

class Solution:
    """
    @param numbers: Give an array numbers of n integer
    @param target : An integer
    @return : return the sum of the three integers, the sum closest target.
    """
    def threeSumClosest(self, numbers, target):
        # write your code here
        if numbers == None or len(numbers) == 0:
            return 0
        diff = sys.maxint
        result = 0
        sorted_array = sorted(numbers)

        for i in range(len(numbers)):
            j = i+1
            k = len(numbers)-1
            while j<k:
                tmp_sum = sorted_array[i] + sorted_array[j] + sorted_array[k]
                if abs(tmp_sum - target) < diff:
                    diff = abs(tmp_sum-target)
                    result = tmp_sum
                if tmp_sum == target:
                    return result
                elif tmp_sum > target:
                    k -= 1
                else:
                    j += 1
        return result