15.三数之和

一、问题描述

给定一个包含 n 个整数的数组 nums，判断是否可以在该数组中找到三个整数，使得它们的和为 0。

示例：

输入：nums = [-1, 0, 1, 2, -1, -4]
输出：true
解释：
与 [-1, -1, 2] 相加得到 0

二、方案一：暴力法

1、思路

暴力法是最直观的方法。通过三重循环遍历数组中的所有三个数字组合，然后检查它们的和是否为 0。

2、代码实现

func threeSum(nums []int) [][]int {
    n := len(nums)
    result := [][]int{}
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            for k := j + 1; k < n; k++ {
                if nums[i] + nums[j] + nums[k] == 0 {
                    result = append(result, []int{nums[i], nums[j], nums[k]})
                }
            }
        }
    }
    return result
}

3、复杂度分析

• 时间复杂度：O(n^3)，其中 n 是数组的长度。最坏的情况下可能需要对每个元素进行 n-1 次比较。
• 空间复杂度：O(1)，因为只使用了常数级别的额外空间。

三、方案二：排序 + 双指针法

1、思路

首先对数组进行排序，然后使用两个指针分别遍历数组，一个从左到右，一个从右到左。对于每个元素，我们尝试找到一个与它相加等于 0 的元素对。如果找到，则记录这个元素对。如果遍历完数组还没有找到这样的元素对，则说明不存在这样的三个数。

2、代码实现

func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    result := [][]int{}
    for i := 0; i < len(nums)-2; 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 {
                result = append(result, []int{nums[i], nums[left], nums[right]})
                left++
                right--
                for left < right && nums[left] == nums[left-1] {
                    left++
                }
                for left < right && nums[right] == nums[right+1] {
                    right--
                }
            }
        }
    }
    return result
}

3、复杂度分析

• 时间复杂度：O(n^2)，其中 n 是数组的长度。排序的时间复杂度是 O(n log n)，之后的两重循环是 O(n^2)。
• 空间复杂度：O(1)，因为只使用了常数级别的额外空间。

四、总结

方案	时间复杂度	空间复杂度	优点	缺点
暴力法	O(n^3)	O(1)	实现简单	效率低
排序 + 双指针法	O(n^2)	O(1)	效率高	需要排序，增加了时间复杂度

推荐使用排序 + 双指针法，因为它在处理大规模数据时更加高效。