資訊專欄INFORMATION COLUMN
摘要：給定一個包含個整數(shù)的數(shù)組，判斷中是否存在三個元素，，，使得找出所有滿足條件且不重復(fù)的三元組。
給定一個包含 n 個整數(shù)的數(shù)組?nums，判斷?nums?中是否存在三個元素 a，b，c ，使得?a + b + c = 0 ？找出所有滿足條件且不重復(fù)的三元組。
注意：答案中不可以包含重復(fù)的三元組。
例如, 給定數(shù)組 nums = [-1, 0, 1, 2, -1, -4]，
滿足要求的三元組集合為：
[
[-1, 0, 1],
[-1, -1, 2]
]
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
res = []
for k in range(len(nums) - 2):
if nums[k] > 0: #肯定不會超過buns
break
if k > 0 and nums[k] == nums[k - 1]:
continue #跳過已經(jīng)存在的數(shù)組
i, j = k + 1, len(nums) - 1
while i < j:
s = nums[k] + nums[i] + nums[j]
if s < 0: #小了，前指針向后移
i += 1
while i < j and nums[i] == nums[i - 1]: i += 1#找到一個不一樣的
elif s > 0:#大了，后指針向前移
j -= 1
while i < j and nums[j] == nums[j + 1]: j -= 1 #找到一個不一樣的
else:
res.append([nums[k], nums[i], nums[j]])
i += 1
j -= 1
while i < j and nums[i] == nums[i - 1]: i += 1 #找到一個不一樣的
while i < j and nums[j] == nums[j + 1]: j -= 1 #找到一個不一樣的
return res
官方解答
class Solution(object):
def threeSum(self, nums):
dic = {}
res = []
for i in nums:
dic[i] = dic.get(i,0) + 1
pos = [i for i in dic if i > 0]
neg = [i for i in dic if i < 0]
neg.sort()
if 0 in dic and dic[0] >= 3:
res.append([0,0,0])
for i in pos:
for j in neg:
k = -i-j
if k in dic:
if (k==i or k==j) and dic[k] >= 2:
res.append([i,k,j])
elif i > k > j:
res.append([i,k,j])
if k < j:
break
return res
"""
nums.sort()
n = len(nums)
ls = []
for i in range(n):
left = i+1
right = n-1
if i > 0 and nums[i] == nums[i-1]:
left += 1
continue
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
col = [nums[i],nums[left],nums[right]]
ls.append(col)
left += 1
right -= 1
while nums[left] == nums[left-1] and left < right:
left+=1
while nums[right] == nums[right+1] and left < right:
right-=1
if s < 0:
left += 1
elif s > 0:
right -= 1
return ls
"""
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/45237.html
摘要：三數(shù)之和給定一個包含個整數(shù)的數(shù)組，判斷中是否存在三個元素，，，使得找出所有滿足條件且不重復(fù)的三元組。例如給定數(shù)組，滿足要求的三元組集合為答案參考 LeetCode15.三數(shù)之和 JavaScript 給定一個包含 n 個整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？找出所有滿足條件且不重復(fù)的三元組。 注意：答案中不可以包含重...
摘要：題目給你一個包含個整數(shù)的數(shù)組，判斷中是否存在三個元素，，，使得請你找出所有和為且不重復(fù)的三元組。 題目 給你一個包含 n 個整數(shù)的數(shù)組?nums，判斷?nums?中是否存在三個元素 a，b，c ，使得?a + b + c = 0 ？請你找出所有和為 0 且不重復(fù)的三元組。 注意：答案中不可以...
摘要：此專欄文章是對力扣上算法題目各種方法的總結(jié)和歸納整理出最重要的思路和知識重點并以思維導(dǎo)圖形式呈現(xiàn)當然也會加上我對導(dǎo)圖的詳解目的是為了更方便快捷的記憶和回憶算法重點不用每次都重復(fù)看題解畢竟算法不是做了一遍就能完全記住的所 ...
摘要：最接近的三數(shù)之和給定一個包括個整數(shù)的數(shù)組和一個目標值。返回這三個數(shù)的和。假定每組輸入只存在唯一答案。例如，給定數(shù)組，，，和與最接近的三個數(shù)的和為答案參考和三數(shù)之和一樣，我先用的循環(huán)，現(xiàn)在用的循環(huán) LeetCode16.最接近的三數(shù)之和 JavaScript 給定一個包括 n 個整數(shù)的數(shù)組 nums 和 一個目標值 target。找出 nums 中的三個整數(shù)，使得它們的和與 target...
閱讀 1275·2021-11-23 09:51
閱讀 2667·2021-09-03 10:47
閱讀 2249·2019-08-30 15:53
閱讀 2435·2019-08-30 15:44
閱讀 1386·2019-08-30 15:44
閱讀 1211·2019-08-30 10:57
閱讀 1938·2019-08-29 12:25
閱讀 1101·2019-08-26 11:57
