最接近的三数之和

yingl · yingl · commit 02b88feac5f5 · 2016-08-03T23:30:57.000+08:00
diff --git a/3sum_closest.py b/3sum_closest.py
@@ -0,0 +1,28 @@
+# -*- coding: utf-8 -*-
+
+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
+        ret = -1
+        min_diff = 2147483647
+        numbers.sort()  # &#20808;&#25490;&#24207;&#65292;&#25490;&#24207;&#21518;&#20004;&#20010;&#25351;&#38024;&#20174;&#22836;&#23614;&#21521;&#20013;&#38388;&#25214;&#12290;
+        for i in xrange(len(numbers) - 2):
+            start, end = i + 1, len(numbers) - 1
+            while start < end:
+                three_sum = numbers[i] + numbers[start] + numbers[end]
+                diff = abs(three_sum - target)
+                if diff == 0:
+                    return target
+                if diff < min_diff:
+                    min_diff = diff
+                    ret = three_sum
+                if three_sum < target:
+                    start += 1
+                else:
+                    end -= 1
+        return ret
