leetcode第16題,和3sum題類似,但是思路很不一樣,要求在數組中找出三個數,使得三個數的和最接近目標數。
這道題最明顯的解法是雙指針法,主要思路是,先對數組排序,之后從頭開始遍歷,遍歷過程中使用雙指針,一個指向開頭,一個指向結尾,三個數加和,求取和目標數的差距,如果差距為正,說明加和過大,應該向小的方向調整,所以end指針應該向左移動,同理,如果差距小于0,start指針向右移動,因為數組已經有序,這樣移動肯定可以滿足調整的要求。
注意合適使用abs,只有在衡量差距與最小差距的相對大小時候,才使用abs。
def threeSumClosest(self, nums, target): nums.sort() n = len(nums) minNum = 9999999 for i in range(n): start = i+1 end = n-1 while start < end: tmp = nums[i]+nums[start]+nums[end]-target if abs(tmp) < abs(minNum): minNum = tmp if minNum == 0: return target elif tmp < 0: start += 1 elif tmp > 0: end -= 1 return minNum+target新聞熱點
疑難解答