LeetCode-in-All
15. 3Sum
Medium
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
Solution
import "sort"
func threeSum(nums []int) [][]int {
sort.Ints(nums)
var res [][]int
for i, a := range nums {
if a > 0 {
break
}
if i > 0 && a == nums[i-1] {
continue
}
l, r := i+1, len(nums)-1
for l < r {
sum := a + nums[l] + nums[r]
if sum < 0 {
l++
} else if sum > 0 {
r--
} else {
res = append(res, []int{a, nums[l], nums[r]})
for l < r && nums[l] == nums[l+1] {
l++
}
for l < r && nums[r] == nums[r-1] {
r--
}
l++
r--
}
}
}
return res
}