15. 三数之和

https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked

首先对数组进行排序，然后使用三重循环（外层固定一个数，内层双指针）寻找满足条件的三个数。关键点包括：1) 排序后跳过重复元素避免重复解；2) 使用双指针技巧将时间复杂度从O(n³)优化到O(n²)；3) 当和为0时同时移动左右指针并跳过重复值。

func threeSum(nums []int) [][]int {
	// 先对数组进行升序排序
	sort.Ints(nums)
	res := make([][]int, 0)
	// 遍历数组
	for i := 0; i < len(nums); i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		left, right := i + 1, len(nums) - 1
		for left < right {
			sum := nums[i] + nums[left] + nums[right]
			if sum < 0 { // 需要数大一点，只能移动左指针
				left++
			} else if sum > 0 { // 需要数小一点，只能移动右指针
				right--
			} else {
				res = append(res, []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 res
}