LC 15 - 3Sum
Question
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:
1
2
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
Example 2:
1
2
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:
1
2
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
Constraints:
3 <= nums.length <= 3000-105 <= nums[i] <= 105
Links
Question here and Solution here
Solution
concept
The main idea is to first sort the array, and fix the first element as the potential candidate. We then use the same methods in LC167 - Two Sum II Input Array Is Sorted to deal with the rest of the 2 elements.
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
for i, a in enumerate(nums): # fix the first element
if a > 0: # if the first element alreadt > 0, not point continue as all num will be bigger than 0 since it is sorted
break
if i > 0 and a == nums[i - 1]:
continue
l, r = i + 1, len(nums) - 1 # use two pointers here
while l < r:
threeSum = a + nums[l] + nums[r]
if threeSum > 0:
r -= 1
elif threeSum < 0:
l += 1
else:
res.append([a, nums[l], nums[r]])
l += 1
r -= 1
while nums[l] == nums[l - 1] and l < r: # only need to take care of one pointer, the other will update itself
l += 1 # the r pointer will be adjusted due to sum(l, r) has to be 0, it will be moved to the left if sum is too big so no duplicate here, if sum is still to small then r wont move but l is already at a new number.
return res
Complexity
time complexity: $O(n^2)$
space complexity: - $O(n)$ or $O(1)$ extra space depending on the sorting algorithm - $O(m)$ for the sorted list