18.四数之和

一、问题描述

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a、b、c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

1. 答案中不可以包含重复的四元组。
2. 调用返回值时，注意不要返回 nums 本身的引用。

示例：

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

二、方案一：暴力法

1、思路

暴力法是最直观的方法，通过四重循环遍历所有可能的四元组组合，然后检查它们的和是否等于目标值。为了确保不返回重复的四元组，我们需要对结果进行去重处理。

2、代码实现

func fourSum(nums []int, target int) [][]int {
    // 对数组进行排序，方便后续去重
    sort.Ints(nums)
    result := make([][]int, 0)
    length := len(nums)

    // 第一层循环，固定第一个数
    for i := 0; i < length-3; i++ {
        // 跳过重复的元素
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        // 第二层循环，固定第二个数
        for j := i + 1; j < length-2; j++ {
            // 跳过重复的元素
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }
            // 第三层循环，固定第三个数
            for k := j + 1; k < length-1; k++ {
                // 跳过重复的元素
                if k > j+1 && nums[k] == nums[k-1] {
                    continue
                }
                // 第四层循环，固定第四个数
                for l := k + 1; l < length; l++ {
                    // 跳过重复的元素
                    if l > k+1 && nums[l] == nums[l-1] {
                        continue
                    }
                    // 检查当前四元组的和是否等于目标值
                    if nums[i]+nums[j]+nums[k]+nums[l] == target {
                        // 如果是，添加到结果中
                        result = append(result, []int{nums[i], nums[j], nums[k], nums[l]})
                    }
                }
            }
        }
    }
    // 返回结果
    return result
}

3、复杂度分析

• 时间复杂度：O(n^4)，因为有四层循环。
• 空间复杂度：O(log n)，主要用于排序。

三、方案二：双指针法

1、思路

双指针法是更高效的解决方案。首先对数组进行排序，然后固定前两个数，再使用双指针查找后两个数。这样可以减少不必要的比较，从而提高效率。

2、代码实现

func fourSum(nums []int, target int) [][]int {
    // 对数组进行排序
    sort.Ints(nums)
    result := make([][]int, 0)
    length := len(nums)

    // 第一层循环，固定第一个数
    for i := 0; i < length-3; i++ {
        // 跳过重复的元素
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        // 第二层循环，固定第二个数
        for j := i + 1; j < length-2; j++ {
            // 跳过重复的元素
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }
            // 初始化左右指针
            left, right := j+1, length-1
            // 使用双指针查找剩余的两个数
            for left < right {
                // 计算当前四元组的和
                sum := nums[i] + nums[j] + nums[left] + nums[right]
                // 检查和是否等于目标值
                if sum == target {
                    // 如果是，添加到结果中
                    result = append(result, []int{nums[i], nums[j], nums[left], nums[right]})
                    // 跳过重复的元素
                    for left < right && nums[left] == nums[left+1] {
                        left++
                    }
                    // 跳过重复的元素
                    for left < right && nums[right] == nums[right-1] {
                        right--
                    }
                    // 移动指针
                    left++
                    right--
                } else if sum < target {
                    // 如果和小于目标值，移动左指针
                    left++
                } else {
                    // 如果和大于目标值，移动右指针
                    right--
                }
            }
        }
    }
    // 返回结果
    return result
}

3、复杂度分析

• 时间复杂度：O(n^3)，虽然有三层循环，但内部的双指针操作使得整体效率更高。
• 空间复杂度：O(log n)，主要用于排序。

四、总结

方案	时间复杂度	空间复杂度	备注
暴力法	O(n^4)	O(log n)	最直观，但效率低下
双指针法	O(n^3)	O(log n)	更高效，但逻辑稍复杂