15. 3Sum
Array, Two Pointers, Sorting, Review ·Problem Statement
link: LeetCode.cn LeetCode
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:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Input: nums = [0,1,1]
Output: []
Input: nums = [0,0,0]
Output: [[0,0,0]]
Solution Approach
The algorithm sorts the array and utilizes a two-pointer technique to find triplets whose sum is zero while avoiding duplicates by skipping repeated elements, and returns the result.
Algorithm
- Sorting: Sort the input array to facilitate the efficient search for triplets.
- Two-pointer Technique: Utilize a two-pointer technique within a loop to find triplets with a sum of zero. Move pointers based on the current sum:
- Increment the left pointer if the sum is less than zero. Decrement the right pointer if the sum is greater than zero. Avoiding Duplicates: Skip duplicate elements during iteration to ensure unique triplets in the result. This includes skipping duplicate elements for the first element (i), as well as for the second (j) and third (k) pointers within the loop.
Implement
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
res = []
nums.sort()
for i in range(n - 2):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
j = i + 1
k = n - 1
while j < k:
temp_sum = nums[i] + nums[j] + nums[k]
if temp_sum == 0:
res.append([nums[i], nums[j], nums[k]])
while j + 1 < k and nums[j] == nums[j + 1]:
j += 1
while k - 1 > j and nums[k] == nums[k - 1]:
k -= 1
j += 1
k -= 1
if temp_sum < 0:
j += 1
if temp_sum > 0:
k -= 1
return res