题目链接：https://leetcode.cn/problems/3sum/
思想
方法：双指针
直接想法
我们遍历数组元素为x，双指针Left和Right，Left从x后一位开始移动，Right从数组最后一位开始移动，同时只能有一个指针在动，使得x + Left + Right == 0。
算法
- 特判，对于数组长度 n < 3，返回 nil。
- 对数组进行排序
- 初始化一个ans的二维切片
- 循环遍历数组
。若nums[i] > 0，则表示后面的元素不管如何搭配都不可能等于0，可以直接跳出循环
。重复元素则跳过，避免出现重复答案
。令左指针 j = i + 1、右指针 k = n - 1, a = nums[i] + nums[j] + nums[k], 当j < k 时 执行循环
1.a > 0, 表示右指针元素过大，需k–
2.a < 0，表示左指针元素过小，需j++
3.a == 0， 将三元组添加到ans数组里，使j，k跳过当前重复元素，直到循环结束
代码示例
func threeSum(nums []int) [][]int { if len(nums) < 3{ return nil } n := len(nums) sort.Ints(nums) ans := make([][]int, 0) for i := 0; i < n - 2; i++{ if nums[i] > 0{ break } if i != 0 && nums[i] == nums[i - 1]{ continue } j := i + 1 k := n - 1 for j < k { a := nums[i] + nums[j] + nums[k] if a > 0{ k-- }else if a < 0 { j++ }else{ ans = append(ans, []int{nums[i], nums[j], nums[k]}) j++ k-- for j < k && nums[j] == nums[j - 1]{ j++ } for j < k && nums[k] == nums[k + 1]{ k-- } } } } return ans }
复杂度分析
- 时间复杂度：O(n2) 其中n表示数组长度，每个元素双指针都会遍历一次数组
- 空间复杂度：O(1) 没有额外的空间
