基础数组问题 - 15.三数之和 - 《LeetCode笔记》

排序 + 双指针
算法流程：
">

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

排序 + 双指针

本题的难点在于如何去除重复解。

算法流程：

特判，对于数组长度 nn，如果数组为 nullnull 或者数组长度小于 33，返回 [][]。
对数组进行排序。
遍历排序后数组：
- 若 nums[i]>0nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 00，直接返回结果。
- 对于重复元素：跳过，避免出现重复解
- 令左指针 L=i+1L=i+1，右指针 R=n-1R=n−1，当 L<RL<R 时，执行循环：
  - 当 nums[i]+nums[L]+nums[R]==0nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,RL,R 移到下一位置，寻找新的解
  - 若和大于 00，说明 nums[R]nums[R] 太大，RR 左移
  - 若和小于 00，说明 nums[L]nums[L] 太小，LL 右移

思路

外层循环：指针 i 遍历数组。
内层循环：用双指针，去寻找满足三数之和 == 0 的元素

先排序的意义

便于跳过重复元素，如果当前元素和前一个元素相同，跳过。

双指针的移动时，避免出现重复解

找到一个解后，左右指针同时向内收缩，为了避免指向重复的元素，需要：

左指针在保证left < right的前提下，一直右移，直到指向不重复的元素
右指针在保证left < right的前提下，一直左移，直到指向不重复的元素
小优化
排序后，如果外层遍历的数已经大于0，则另外两个数一定大于0，sum不会等于0，直接break。 ```go ////碰撞指针法，考察边界思维，注意去重的多种情况 //1.不足三位数的排除 //2.全部为正数的排除 //3.【-1，-1，-2，0，1，2，3，3】 //3.1排除两个重复的首数-1的结果【-1，0，1】 //3.2排除两个重复的尾数3的结果【-1，-2，3】

func threeSum(nums []int) [][]int { sort.Ints(nums) res := [][]int{}

for i:=0 ;i<len(nums)-2;i++{
    n1 := nums[i]
    if n1>0{
        break
    }
    if i >0 && n1 ==nums[i-1]{
        continue
    }
    l := i+1
    r := len(nums)-1 
    for l<r {
        n2,n3 := nums[l],nums[r]
        if n1+n2+n3 == 0 {
            res = append(res, []int{n1,n2,n3}) 
            for l<r && nums[l] == n2 {
                l++
            }
            for l<r && nums[r] == n3 {
                r--
            }        
        }else if n1+n2+n3<0 {
            l++
        }else {
            r--
        }
    }
}
return res

}

```go
// 补一个 golang 版本的,更好理解，包含细节
func threeSum(nums []int) [][]int {
    // 先从小到大排序
    sort.Ints(nums)
    // 接收结果,定义二维数组=切片，存放res结果
    var res [][]int
    // 获取数组长度
    length := len(nums)
    // 边界处理，数字不足三个直接返回空
    if len(nums) < 3 {
        return res
    }
    // 开始循环第一个固定值
    for index, value := range nums {
        // 如果固定位的值已经大于0，因为已经排好序了，后面的两个指针对应的值也肯定大于0，则和不可能为/，所以返回
        if nums[index] > 0 {
            return res
        }
        // 排除值重复的固定位
        if index > 0 && nums[index] == nums[index-1] {
        //if nums[index] == nums[index-1] {     //会爆一维数组越界问题range【-1】
            continue
        }
        // 指针初始位置，固定位右边第一个和数组最后一个
        l := index + 1
        r := length - 1
        // 开始移动两个指针
        for l < r {
            // 判断三个数字之和的三种情况
            sum := value + nums[l] + nums[r]
            switch {
            case sum == 0:
                // 将结果加入二元组,切片操作res=append(res,a,b...)
                res = append(res, []int{nums[index], nums[l], nums[r]})
                // 去重，如果l < r且下一个数字一样，则继续挪动
                for l < r && nums[l] == nums[l+1] {
                    l += 1
                }
                // 同理
                for l < r && nums[r] == nums[r-1] {
                    r -= 1
                }
                l += 1
                r -= 1
            case sum > 0:
                // 如果和大于 0，那就说明 right 的值太大，需要左移
                r -= 1
                // 如果和小于 0，那就说明 left 的值太小，需要右移 
            case sum < 0:
                l += 1
            }
        }
    }
    return res
}

15.三数之和

排序 + 双指针

算法流程：

思路

先排序的意义

双指针的移动时，避免出现重复解

小优化