18. 四数之和

题目

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target
  你可以按 任意顺序 返回答案 。

难度：🌟🌟🌟🌟

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
 
提示：

• 1 <= nums.length <= 200
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹

题解

和三数之和类似，本题在三数之和解法的基础上，通过将四数之和转化为三数之和，再把三数之和转化为两数之和，最终合并结果。

代码实现

func fourSum(nums []int, target int) [][]int {
	sort.Ints(nums)
	n := len(nums)
	var res [][]int
	for i := 0; i < n-3; i++ {
		// 三数之和
		threeSumRes := threeSumHelper(nums, i+1, target-nums[i])
		for _, ts := range threeSumRes {
			var t []int
			t = append(t, nums[i])
			t = append(t, ts...)
			res = append(res, t)
		}
		for i < n-3 && nums[i+1] == nums[i] {
			i++
		}
	}
	return res
}

// threeSumHelper 返回等于 target 的三数之和
// start nums数组开始的下标
// target 目标数
func threeSumHelper(nums []int, start, target int) [][]int {
	n := len(nums)
	var res [][]int
	for i := start; i < n-2; i++ {
		// 两数之和
		twoSumRes := twoSumHelper(nums, i+1, target-nums[i])
		for _, ts := range twoSumRes {
			var t []int
			t = append(t, nums[i])
			t = append(t, ts...)
			res = append(res, t)
		}
		for i < n-2 && nums[i+1] == nums[i] {
			i++
		}
	}
	return res
}

func twoSumHelper(nums []int, start, target int) [][]int {
	low, high := start, len(nums)-1
	var res [][]int
	for low < high {
		ts := nums[low] + nums[high]
		left, right := nums[low], nums[high]
		if ts > target {
			high--
		} else if ts < target {
			low++
		} else if ts == target {
			res = append(res, []int{nums[low], nums[high]})
			for low < high && nums[low] == left {
				low++
			}
			for low < high && nums[high] == right {
				high--
			}
		}
	}
	return res
}