18. 四数之和

leecode原题

题目

给你一个由 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
• -109 <= nums[i] <= 109
• -109 <= target <= 109

解题思路

思路

这道题详细讲解，建议直接参考代码随想录

另外整体思路跟解法跟三数之和是类似的，只是多了一层循环。参考三数之和

实现

源码

func fourSum(nums []int, target int) [][]int {
    res := make([][]int, 0)
    if len(nums) < 4 {
        return nil
    }
    sort.Ints(nums) // 数组先排序
    // 第一层循环
    for i := 0; i < len(nums)-3; i++ {
        n1 := nums[i]
        // n1去重
        if i > 0 && nums[i-1] == n1 {
            continue
        }
        // 第二层循环
        for j := i + 1; j < len(nums)-2; j++ {
            n2 := nums[j]
            // n2去重
            if j > i+1 && nums[j-1] == n2 {
                continue
            }
            left := j + 1
            right := len(nums) - 1
            // 移动left和right指针直到相遇
            for left < right {
                n3 := nums[left]
                n4 := nums[right]
                sum := n1 + n2 + n3 + n4
                if sum > target {
                    // 像数值小的方向移动, 即rigth指针向左移动
                    right--
                } else if sum < target {
                    // 向数值大的方向，即向右移动
                    left++
                } else {
                    res = append(res, []int{n1, n2, n3, n4})
                    // left去重
                    for left < right && nums[left] == n3 {
                        left++
                    }
                    // right去重
                    for left < right && nums[right] == n4 {
                        right--
                    }
                }
            }
        }
    }
    return res
}