15、三数の和(python)
9086 ワード
タイトル:
n個の整数を含む配列numsを与えて、numsの中に3つの要素a,b,cが存在するかどうかを判断して、a+b+c=0にしますか?条件を満たし、繰り返さないすべての三元グループを見つけてください.
注意:答えに重複する三元グループは含まれてはいけません.
例:
コード(ソート+ダブルポインタ):
n個の整数を含む配列numsを与えて、numsの中に3つの要素a,b,cが存在するかどうかを判断して、a+b+c=0にしますか?条件を満たし、繰り返さないすべての三元グループを見つけてください.
注意:答えに重複する三元グループは含まれてはいけません.
例:
nums = [-1, 0, 1, 2, -1, -4],
:
[
[-1, 0, 1],
[-1, -1, 2]
]
コード(ソート+ダブルポインタ):
class Solution:
def threeSum(self, nums):
if len(nums) < 3: # < 3,
return []
nums = sorted(nums) #
re = [] #
for i in range(len(nums)): #
if nums[i] > 0: # nums[i] > 0, 0, re
return re
if i > 0 and nums[i] == nums[i-1]: #
continue
L = i + 1 #
R = len(nums) - 1 #
while L < R: #
temp = nums[i] + nums[L] + nums[R] #
if temp == 0: # temp = 0
re.append([nums[i],nums[L],nums[R]]) #
while L < R and nums[L] == nums[L+1]: # ,
L = L + 1
while L < R and nums[R] == nums[R-1]: # ,
R = R - 1
L = L + 1 # ,
R = R - 1 # ,
elif temp > 0: # temp > 0
R = R - 1 # ,
else:
L = L + 1 # , ,
return re