Leetcode - 3Sum
https://leetcode.com/problems/3sum/
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
Typical 3sum problem. For removing duplicate result, it can use a helper to find next uniq element to update i, j, k.
func threeSum(nums []int) [][]int {
if len(nums) == 0 {
return [][]int{}
}
sort.Ints(nums)
result := [][]int{}
i := 0
for i < len(nums) {
j := i+1
k := len(nums)-1
for j < k {
sum := nums[i] + nums[j] + nums[k]
if sum == 0 {
result = append(result, []int{nums[i], nums[j], nums[k]})
}
if sum > 0 {
prevK := nums[k]
for k > j && nums[k] == prevK {
k--
}
} else {
prevJ := nums[j]
for j < k && nums[j] == prevJ {
j++
}
}
}
prevI := nums[i]
for i < len(nums) && nums[i] == prevI {
i++
}
}
return result
}
评论 (0)
