Three Sum with duplicated values
1. Link
2. 描述
给出一个有n个元素的数组S,S中是否有元素a,b,c满足a+b+c=0?找出数组S中所有满足条件的三元组。注意:
三元组(a、b、c)中的元素必须按非降序排列。(即a≤b≤c)
解集中不能包含重复的三元组。
例如,给定的数组 S = {-10 0 10 20 -10 -40},解集为(-10, -10, 20),(-10, 0, 10)
0 <= S.length <= 1000
示例1
输入:
[0]
复制返回值:
[]
复制
示例2
输入:
[-2,0,1,1,2]
复制返回值:
[[-2,0,2],[-2,1,1]]
3. 思路
sort array
iterate every element num[i]
binary search for the remaining element to check if two sum to target = 0- num[i] exist
skip all duplicated values once the first element found to avoid duplicated results
Time: O(nlogn) for sorting O(n ) for the first loop, O(n) for binary search in worst case, so O(n^2 + nlogn) = O(n^2)
Space O(1)
4. Coding
#
#
# @param num int整型一维数组
# @return int整型二维数组
#
class Solution:
def threeSum(self , num ):
# write code here
if not num or len(num) <3:
return []
res = []
num.sort()
i = 0
while i < len(num):
target = 0 - num[i]
sol = [num[i]]
# two sum with binary search
left, right = i+1, len(num)-1
while left < right:
tmp = num[left] + num[right]
if tmp < target:
left += 1
elif tmp > target:
right -= 1
else:
sol.append(num[left])
sol.append(num[right])
sol.sort()
res.append(sol[:])
sol =[num[i]]
left_idx = left+1
# skip all duplicated value to avoid duplicated result
while left_idx <right and num[left] == num[left_idx]:
left_idx += 1
left = left_idx
right_idx = right-1
while right_idx >left and num[right] == num[right_idx]:
right_idx -= 1
right = right_idx
# skip all duplicated element
idx = i + 1
while idx<len(num) and num[idx] == num[i]:
idx += 1
i = idx
return res
Last updated
Was this helpful?