Friday, September 12, 2014

Leetcode: 3Sum Closest @Python

class Solution:
    # @return an integer
    def threeSumClosest(self, num, target):
        A=sorted(num)
        n=len(A)
        rst=[A[0],A[1],A[2]]
        crt=abs(A[0]+A[1]+A[2]-target)
        for k in range(n-2):
            a=A[k]
            if k>0 and a==A[k-1]:
                continue
            i=k+1
            j=n-1
            while j>i:
                gap=A[i]+A[j]+A[k]-target
                if abs(gap)<crt:
                    rst=[A[k],A[i],A[j]]
                    crt=abs(gap)
                while j>i:
                    if A[i]+A[j]+A[k]-target>0:
                        j-=1
                        if A[j]!=A[j+1]:
                            break
                    else:
                        i+=1
                        if A[i]!=A[i-1]:
                            break
        return sum(rst)

No comments :

Post a Comment