0015－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.

Notice that the solution set must not contain duplicate triplets.

  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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66  func threeSum(nums []int) [][]int { var ans [][]int if len(nums) < 3 { return ans } var nbs []int var nb2s []int cnt0 := 0 table := make(map[int]int) for _, n := range nums { if n == 0 { cnt0++ } _, has := table[n] if has { table[n]++ if table[n] == 2 { nb2s = append(nb2s, n) } } else { table[n] = 1 nbs = append(nbs, n) } } if cnt0 > 2 { ans = append(ans, []int{0, 0, 0}) } for _, n1 := range nb2s { if n1 == 0 { continue } n2 := -2 * n1 _, ok2 := table[n2] if ok2 { ans = append(ans, []int{n1, n1, n2}) } } sort.Ints(nbs) for i1 := 0; i1 < len(nbs)-1; i1++ { n1 := nbs[i1] if n1 > 0 { break } for i2 := i1 + 1; i2 < len(nbs); i2++ { n2 := nbs[i2] if n1+n2 > 0 { break } n3 := -n1 - n2 if n1 >= n3 || n2 >= n3 { continue } _, ok := table[n3] if ok { ans = append(ans, []int{n1, n2, n3}) } } } return ans }