動機
複習3sum
Problem
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]]
such that i != j
, i != k
, and j != k
, and nums[i] + nums[j] + nums[k] == 0
.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]Output: [[-1,-1,2],[-1,0,1]]
Example 2:
Input: nums = []Output: []
Example 3:
Input: nums = [0]Output: []
Constraints:
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
sol
列舉不難,但是要去重複很麻煩,所以在加的時候就要看有沒有重複
反覆做2sum並一直丟掉最小的數字
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
ret = []
nums.sort()
for (i,n) in enumerate(nums):
a, b = [i+1, len(nums)-1]
while a < b:
tmp = n+nums[a]+nums[b]
if tmp == 0:
tmp = [n,nums[a],nums[b]]
tmp.sort()
if tmp not in ret:
ret.append(tmp)
b -= 1
a += 1
elif tmp > 0:
b -= 1
else:
a += 1
return ret