<feat> add problem 16 3Sum Closest

bluedazzle · bluedazzle · commit 63b0c46bd917 · 2016-11-11T14:11:06.000+08:00
Author:rapospectre@gmail.com

Desc: add problem 16 3Sum Closest
diff --git a/readme.md b/readme.md
@@ -26,6 +26,8 @@
 **&#21160;&#24577;&#35268;&#21010;&#24605;&#36335;: &#22797;&#26434;&#24230; O(n2), &#29366;&#24577;&#26159;: n &#20010;&#23383;&#31526;&#20018; n <= len(strs) &#30340;&#26368;&#38271;&#20844;&#20849;&#21069;&#32512;, &#36716;&#31227;&#26041;&#31243;: D(n) = min{D(n-1), L(j)}, 0 <= j <= min{D(n-1), len(str(n))} (&#22823;&#27010;&#26159;&#36825;&#26679;)**
 #### 15. [3Sum][30]: [Solution][31] 
 **tips: [K Sum Problem][32]**
+#### 16. [3Sum Closest][32]: [Solution][33]
+**tips: &#21487;&#20197;&#30475;&#20316;&#26159;&#26377;&#20010;&#22266;&#23450;&#25968;&#23383;&#30340; 4 Sum &#38382;&#39064;,&#31245;&#24494;&#25913;&#19979; 3 Sum &#20195;&#30721;&#21363;&#21487;, &#26102;&#38388;&#22797;&#26434;&#24230;&#19981;&#22686;&#21152; O(nlogn)**
 
 [1]: https://leetcode.com/problems/two-sum/
 [2]: https://github.com/bluedazzle/leetcode_python/blob/master/src/two_sum.py
@@ -58,4 +60,6 @@
 [29]: https://github.com/bluedazzle/leetcode_python/blob/master/src/longest_common_prefix.py
 [30]: https://leetcode.com/problems/3sum/
 [31]: https://github.com/bluedazzle/leetcode_python/blob/master/src/3sum.py
-[32]: http://blog.csdn.net/nanjunxiao/article/details/12524405
+[32]: http://blog.csdn.net/nanjunxiao/article/details/12524405
+[33]: https://leetcode.com/problems/3sum-closest/
+[34]: https://github.com/bluedazzle/leetcode_python/blob/master/src/3sum_closest.py
diff --git a/src/3sum_closest.py b/src/3sum_closest.py
@@ -0,0 +1,55 @@
+# coding: utf-8
+#                                                    ##       ##
+#                                                  #####   #  ####
+#                                               ######### ## #######
+#                                              ###  ############ ##
+#                               ####          #     ####### #########
+#  ###########               #########       #      ###########  ##
+# #############             ###    ####        ##  #### ########                                     ##
+# ##   ##    ##            ##        ###     #########  #########        ###         ##       #     ###      ##      #
+#      ##   ##                    ## ###    ########   ##########       #### ##     ###     ####   ###    #####    ####
+#     ## ####                     ##  ##   #########   ##########      ########    #####   ####    ####   #####   #####
+#    ######          ####        ##   ##  ### ## ###  ############    ## ### ##   ## ##   ###      ###    #####  ### ##
+#    ####           #####        ##  ###  ###  ###### ############       ##  ##  #####    ### ##  ###     ###    #####
+#   ## ##         ### ###       ###  ###   ######### ##############     ### ##   ####     ## ###  #####  ####    ####
+#   ## ###        ##  ##        ##  ###     #####    ##############    #######    #####   #####   #####  ###     ######
+#  ##   ###  ##  #######        ######              ###############    ####         ##     ##       #              ###
+#  ##   ######   #######       #####               #################   ###
+# ##      ###     ##  ##       ###                  #################  ##
+# ##                           ##                 ###################  ##
+# ##                          ###                  ######################
+#                             ##                    #               ## #
+#                             ##
+# author: RaPoSpectre
+# time: 2016-11-11
+
+
+class Solution(object):
+    def threeSumClosest(self, nums, target):
+        """
+        :type nums: List[int]
+        :rtype: List[List[int]]
+        """
+        nums.sort()
+        close = 1000
+        res = 0
+        for i in xrange(0, len(nums) - 1):
+            starget = target - nums[i]
+            x = i + 1
+            y = len(nums) - 1
+            while x < y:
+                midres = nums[x] + nums[y]
+                if midres == starget:
+                    return target
+                elif midres > starget:
+                    y -= 1
+                else:
+                    x += 1
+                l = abs(midres - starget)
+                if l < close:
+                    close = l
+                    res = midres + nums[i]
+        return res
+
+
+# print Solution().threeSum([-1, 2, 1, -4], -2)
