15.md

15. 3Sum

Leetcode 链接

题意解析

找出数组中的三个数，其和为 0。注意找出的数组需要进行去重，例如 [-1, 0, 1] 和 [1, 0, -1] 只能算同一组。

解决方案

最直接的思路肯定就是用三重循环遍历，但是这样会超时并且无法解决去重的问题。

所以应该改用 "双指针" 的思路，由于是对数组处理，所以此处 "指针" 其实指的就是数组下标。

注意以下代码中 "shrink" 函数的思路。

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

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

		var (
			left  = i + 1
			right = len(nums) - 1
		)

		for left < right {
			val := nums[i] + nums[left] + nums[right]

			switch {
			case val == 0:
				left, right = shrink(nums, left, right)
				res = append(res, []int{nums[i], nums[left], nums[right]})
				left, right = left+1, right-1

			case val < 0:
				left++

			case val > 0:
				right--
			}
		}
	}

	return res
}

func shrink(nums []int, left, right int) (int, int) {
	for left < len(nums)-1 && nums[left] == nums[left+1] {
		left++
	}

	for right-1 > left && nums[right] == nums[right-1] {
		right--
	}

	return left, right
}