15-三数之和

题目

三数之和这道算法题的解题思路和代码实现通常遵循以下步骤：

排序：首先对数组进行排序，以便使用双指针技术。
外层循环：遍历数组中的每个元素，将三数之和问题转化为两数之和问题。
避免重复：跳过与前一个元素相同的元素以避免重复的解。
双指针：在剩余的数组部分使用两个指针（一个指向开头，一个指向末尾）寻找配对的元素，使它们的和等于目标值。
内层循环：在内层循环中，根据两指针指向的元素之和与目标值的比较，移动指针，并在找到有效组合时添加到结果中。同时，为避免重复，跳过相邻且相同的元素。

下面是 Go 语言实现的示例代码：

package main

import (
    "fmt"
    "sort"
)

func threeSum(nums []int) [][]int {
    sort.Ints(nums) // 对数组进行排序
    n := len(nums)
    res := make([][]int, 0)

    for i := 0; i < n; i++ {
        // 避免重复: 如果当前数字与前一个数字相同，则跳过
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }

        // 将三数之和转化为两数之和，即 nums[i] + nums[j] + nums[k] = 0
        // 等价于 nums[j] + nums[k] = -nums[i]
        target := -nums[i]

        // 双指针
        j, k := i+1, n-1
        for j < k {
            sum := nums[j] + nums[k]
            switch {
            case sum < target: // 如果和小于目标值，则移动左指针
                j++
            case sum > target: // 如果和大于目标值，则移动右指针
                k--
            default: // 找到有效组合
                res = append(res, []int{nums[i], nums[j], nums[k]})
                // 移动指针
                j++
                k--

                // 再跳过重复元素（已经找过这个组合了）
                for j < k && nums[j] == nums[j-1] {
                    j++
                }
                for j < k && nums[k] == nums[k+1] {
                    k--
                }
            }
        }
    }
    return res
}

func main() {
    nums := []int{-1, 0, 1, 2, -1, -4}
    result := threeSum(nums)
    fmt.Println(result)
}

跳过重复元素是为了避免在最终结果中出现重复的三元组。这在“三数之和”这类问题中尤为重要，因为我们的目标是找出所有独特的三元组，其和为零，而不是重复的组合。考虑到数组是排序的，重复的元素将会相邻排列，因此可以通过比较当前元素与前一个元素来轻易地检测重复。

具体地，跳过重复元素的原因包括：

保证结果的唯一性：算法的目标是找出所有不同的三元组，使它们的和为0。如果不跳过重复的元素，那么同样的三元组就会被多次计算并添加到结果中。
提高效率：跳过重复元素还有助于减少不必要的计算。如果对每个重复元素都执行相同的操作，那么会增加计算时间，特别是在有大量重复元素的情况下。
简化逻辑：处理非重复元素可以简化算法的逻辑。因为重复元素会产生相同的结果，所以可以避免在内部循环中进行冗余的检查。

在“三数之和”问题的解决方案中，这种跳过通常发生在两个地方：

主循环中：在处理一个新的元素之前，检查它是否与前一个元素相同。如果是，就跳过它。
双指针循环中：当找到一个有效的三元组后，移动指针并跳过所有相同的元素，以寻找下一个不同的元素组合。

这样做确保了每个三元组是唯一的，并且大大减少了不必要的计算。

提示

在处理“三数之和”问题时，我们需要区分两种类型的“重复”：一种是重复的元素，另一种是重复的三元组。关键在于我们要避免的是重复的三元组，而不是包含重复元素的三元组。

例如示例中，数组 [-1,0,1,2,-1,-4] 中有重复的元素（比如 -1）。但是，由这些元素形成的三元组 [-1, -1, 2] 和 [-1, 0, 1] 是唯一的，因为它们代表着数组中不同的数值组合，即使某些数值在数组中出现了不止一次。

当我们在代码中 “跳过重复元素” 时，我们的目的是避免对于同一个元素重复进行相同的操作，从而导致生成相同的三元组。例如，如果数组中有两个连续的 -1，在确定第一个数字为 -1 后，我们只需要对第一个 -1 进行操作，而不是对每一个 -1 都重复相同的查找过程。

在具体实现中，这通常是通过以下方式完成的：

在外层循环中，如果当前元素与前一个元素相同，则跳过当前元素。这是为了防止对于相同的第一个元素重复查找两数之和。
在找到一个有效的三元组后，当移动内层循环的指针以寻找新的组合时，跳过与当前指针相同的元素。这是为了避免在已经确定了前两个元素的情况下，对于相同的第三个元素重复添加相同的三元组。

这样，我们确保每个三元组只被添加一次，即使某些元素在数组中出现了多次。

题目​

题目