题目
- 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]
- ]
- V1
- func threeSum(nums []int) [][]int {
- numCnt := make(map[int]int)
- for _, num := range nums {
- if num != 0 && numCnt[num]>= 2 {
- continue
- }
- numCnt[num] = numCnt[num] + 1
- }
- var newNums []int
- for num, cnt := range numCnt {
- for i := 0; i <3 && i < cnt; i++ {
- newNums = append(newNums, num)
- }
- }
- sort.Ints(newNums[:])
- nums = newNums
- var result [][]int
- uniq := make(map[string]bool)
- for i := 0; i < len(nums); i++ {
- if i> 0 && nums[i] == nums[i-1] {
- continue
- }
- for j := i + 1; j <len(nums); j++ {
- if j> j+1 && nums[j] == nums[j-1] {
- continue
- }
- expected := 0 - nums[i] - nums[j]
- cnt := numCnt[expected]
- if expected <nums[j] {
- continue
- }
- if expected == nums[i] {
- cnt -= 1
- }
- if expected == nums[j] {
- cnt -= 1
- }
- if cnt <= 0 {
- continue
- }
- tmp := []int{nums[i], nums[j], expected}
- sort.Ints(tmp)
- s, _ := JSON.Marshal(tmp)
- if !uniq[string(s)] {
- result = append(result, tmp)
- uniq[string(s)] = true
- }
- }
- }
- return result
- }
- Runtime: 980 ms, faster than 37.23% of Go online submissions for 3Sum.
- Memory Usage: 339.8 MB, Less than 41.24% of Go online submissions for 3Sum.
- V2
- func threeSum(nums []int) [][]int {
- sort.Ints(nums[:])
- var result [][]int
- for i := 0; i < len(nums)-2; i++ {
- if i> 0 && nums[i] == nums[i-1] {
- continue
- }
- left, right := i+1, len(nums)-1
- for left <right {
- s := nums[i] + nums[left] + nums[right]
- if s < 0 {
- left++
- } else if s> 0 {
- right--
- } else {
- result = append(result, []int{nums[i], nums[left], nums[right]})
- for left < right && nums[left] == nums[left+1] {
- left++
- }
- for left < right && nums[right] == nums[right-1] {
- right--
- }
- left++
- right--
- }
- }
- }
- return result
- }
- Runtime: 876 ms
- Memory Usage: 272.7 MB
来源: http://www.bubuko.com/infodetail-3023838.html