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)
Friday, September 12, 2014
Leetcode: 3Sum Closest @Python
Subscribe to:
Post Comments
(
Atom
)
No comments :
Post a Comment