溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹LeetCode如何解決三數(shù)之和問題，文中介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們一定要看完！
1
題目描述
給定一個整數(shù)數(shù)組nums，判斷nums中是否存在三個元素 a，b，c ，使得 a + b + c = 0 。如不存在返回[]，如存在返回所有滿足條件且不重復(fù)的答案。如：輸入[-1,0,1,2,-1,-4]返回[[-1,0,-1],[-1,-1,2]]，如輸入[-3,3]，返回[]。
2
解題
思路一：哈希表
本題要找到滿足條件的三個元素，當(dāng)固定第一個元素a，則題目轉(zhuǎn)化成找到b、c使得和為-a的問題，即與LeetCode刷題DAY 8：兩數(shù)之和中問題一致，因此也可用哈希表的方法解決。
class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: if len(nums)<3: return [] nums = sorted(nums) a = list() for i in range(len(nums)-2): if i>0 and nums[i]==nums[i-1]: continue h_map = {} target = -nums[i] for j in range(i+1,len(nums)): if target - nums[j] in h_map: a.append(sorted([nums[i],nums[j],target-nums[j]])) h_map[nums[j]]=j return list(set([tuple(t) for t in a]))
思路二：雙指針
當(dāng)對數(shù)組完成排序并固定第一個元素a，則題目與LeetCode刷題DAY 9：兩數(shù)之和II中問題一致，可用雙指針方法解決。
class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: if len(nums)<3: return [] nums = sorted(nums) a = list() for i in range(len(nums)-2): if i>0 and nums[i]==nums[i-1]: continue x = i+1 y = len(nums)-1 target = -nums[i] while x<y: if nums[x]+nums[y] == target: a.append(sorted([nums[i],nums[x],nums[y]])) x += 1 elif nums[x]+nums[y] < target : x += 1 else: y -= 1 return list(set([tuple(t) for t in a])
以上是“LeetCode如何解決三數(shù)之和問題”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對大家有幫助，更多相關(guān)知識，歡迎關(guān)注億速云行業(yè)資訊頻道！
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機(jī)網(wǎng)站二維碼