15. 三数之和

leecode原题

题目

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例

示例 1:

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

示例 2:

输入：nums = []
输出：[]

示例 3:

输入：nums = [0]
输出：[]

提示：

• 0 <= nums.length <= 3000
• -105 <= nums[i] <= 105

解题思路

思路

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

总体来说:

排序 + 双指针

1. nums从小到大排序，i,j,k分别代表元素a,b,c的索引

2. 先固定i,i的范围是区间[0, len(nums)-2)，注意要对a去重，如果nums[i] == nums[i-1]将可能出现三元组重复

3. 固定i后，取j = i+1,k =len(nums)-1，j和k在j<k的情况下（j>i和j<k已经保证j和k在移动过程中不会数组越界）作为双指针进行遍历，判断a+b+c

   • 如果a+b+c==0,则添加三元组,然后j++、k--，并且注意对b,c去重，原因同2中的a

   • 如果a+b+c>0,则k--

   • 如果a+b+c<0,则j++

实现

源码

func threeSum(nums []int) [][]int {
    // 对数组进行从小到大的排序
    sort.Ints(nums)
    res := make([][]int, 0)

    // 定义三个数begin, left, rigth(i, left, right不能相同)
    for i := 0; i < len(nums)-2; i++ { // begin最多到len(nums)-2
        begin := nums[i]
        // 去除begin的重复值
        if i > 0 && begin == nums[i-1] {
            continue
        }
        left := i + 1          // 左指针指向begin前一位
        right := len(nums) - 1 // 右指针指向最后一位
        for left < right {
            sum := nums[i] + nums[left] + nums[right]
            if sum == 0 {
                res = append(res, []int{nums[i], nums[left], nums[right]})
                // left去重
                curLeftValue := nums[left]
                for left < right && curLeftValue == nums[left] {
                    left++
                }
                // right去重
                curRightValue := nums[right]
                for left < right && curRightValue == nums[right] {
                    right--
                }
            } else if sum > 0 {
                // 因为数组已经排序, 所以right应该向数值小的地方移动
                right--
            } else {
                // 因为数组已经排序, 所以left应该向数值大的地方移动
                left++
            }
        }

    }
    return res
}