Algorithms - 15. 3Sum - 《leetcode》

循环二分查找，时间复杂度 n2 ```go func binarySearch(nums []int, expect int, start int) int { if len(nums) == 0 {
```
 return -1
```
}

end := len(nums)

for mid := start + (end - start) / 2; start < end; {
```
 num := nums[mid]
 if num == expect {
     return mid
 }

 if num < expect {
     start = mid + 1
 } else {
     end = mid
 }

 mid = start + (end - start) / 2
```
}

return -1 }

func threeSum(nums []int) [][]int { var result [][]int sort.Ints(nums)

for i, num := range nums {
    if i > 0 && nums[i] == nums[i-1] {
        continue
    }

    for j := i+1; j < len(nums); j++ {
        cur := nums[j]
        expect := -(cur + num)

        if j > i + 1 && nums[j] == nums[j-1] {
            continue
        }

        idx := binarySearch(nums, expect, j+1)
        if idx >= 0 {
            result = append(result, []int{num, cur, nums[idx]})
        }
    }
}

return result

}

func main() { fmt.Println(threeSum([]int{-1, 0, 1, 2, -1, -4})) fmt.Println(threeSum([]int{0,0,0,0})) }


2. 双指针法
```go
func threeSum(nums []int) [][]int {
    var result [][]int
    sort.Ints(nums)

    for i := 0; i < len(nums); i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }

        lo := i + 1
        hi := len(nums) - 1
        for lo < hi {
            sum := nums[i] + nums[lo] + nums[hi]

            if sum < 0 || lo > i+1 && nums[lo] == nums[lo - 1] {
                lo++
            } else if sum > 0 || hi < len(nums) -1 && nums[hi] == nums[hi + 1] {
                hi--
            } else {
                result = append(result, []int{nums[i], nums[lo], nums[hi]})
                lo++
                hi--
            }
        }
    }

    return result
}