紧接着发一题,3SumClosest

看名字就知道和上题有关系,吐槽一下Python2.5以后既然有三目运算符了,但是还不支持stmt1 if condition else stmt2.stmt1和stmt2替换成expr就OK…导致程序最后那个if else 纠结了我半天

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).
View Code PYTHON
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
30
31
class Solution:
    # @return an integer
    def threeSumClosest(self, num, target):
        length = len(num)
 
        if length<3:
            return None
        if length == 3:
            return sum(num)
 
        num = sorted(num)
        ret = 0
        threesum = num[0] + num[1] + num[length-1]
        diff = target - threesum
        for i in range(0,length-2):
            if i>0 and num[i] == num[i-1]:
                continue
            j,k = i + 1, length - 1
            while j < k:
                print num[i],num[j],num[k],num
                threesum = num[i] + num[j] + num[k]
                newDiff = target - threesum
                if abs(newDiff) < abs(diff):
                    diff = newDiff
                    if diff == 0:
                        return threesum
                if newDiff<0:
                    k-=1
                else:
                    j+=1
        return target - diff

 

Share This: 

Leave a Reply

Your email address will not be published. Required fields are marked *