暴力解法,2200ms, 超过5.5%的用户 T.T
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 |
func threeSum(nums []int) [][]int { var r [][]int L := len(nums) if L <= 0 { return r } for i := 0; i < L; i++ { min := i for j := i; j < L; j++ { if nums[j] < nums[min] { min = j } } t := nums[i] nums[i] = nums[min] nums[min] = t } if nums[0] > 0 || nums[L-1] < 0 { return r } for i := 0; i < L; i++ { if i > 0 && nums[i] == nums[i-1] { continue } for j := i + 1; j < L; j++ { if j > i+1 && nums[j] == nums[j-1] { continue } left := nums[i] + nums[j] for k := L - 1; k > j; k-- { if k < L-1 && nums[k] == nums[k+1] { continue } else if nums[k]+left < 0 { break } else if nums[k]+left == 0 { r = append(r, []int{nums[i], nums[j], nums[k]}) break } } } } return r } |
参考评论区大佬解法
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 |
func threeSum(nums []int) [][]int { var res [][]int L := len(nums) if L < 3 { return res } for i := 0; i < L; i++ { min := i for j := i; j < L; j++ { if nums[j] < nums[min] { min = j } } t := nums[i] nums[i] = nums[min] nums[min] = t } if nums[0] > 0 || nums[L-1] < 0 { return res } for i := 0; i < L; i++ { target := nums[i] if target > 0 { break } if i > 0 && nums[i] == nums[i-1] { continue // 去重 } l, r := i+1, L-1 for l < r { sum := nums[l] + nums[r] + target if sum > 0 { r-- } else if sum < 0 { l++ } else if sum == 0 { res = append(res, []int{target, nums[l], nums[r]}) l++ r-- // 去重 for l < r && nums[l] == nums[l-1] { l++ } for l < r && nums[r] == nums[r+1] { r-- } } } } return res } |
5.5%还行