leetcode第16題,和3sum題類似,但是思路很不一樣,要求在數(shù)組中找出三個數(shù),使得三個數(shù)的和最接近目標數(shù)。
這道題最明顯的解法是雙指針法,主要思路是,先對數(shù)組排序,之后從頭開始遍歷,遍歷過程中使用雙指針,一個指向開頭,一個指向結(jié)尾,三個數(shù)加和,求取和目標數(shù)的差距,如果差距為正,說明加和過大,應(yīng)該向小的方向調(diào)整,所以end指針應(yīng)該向左移動,同理,如果差距小于0,start指針向右移動,因為數(shù)組已經(jīng)有序,這樣移動肯定可以滿足調(diào)整的要求。
注意合適使用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新聞熱點
疑難解答