leetcode_015_三数之和解析

三数之和解析

题目

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

暴力解法1

使用3重循环暴力解法

package main

import (
	"fmt"
	"sort"
)

// 使用3重for循环
func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	result := make([][]int, 0)
	for i := 0; i < len(nums); i++ {
		for j := 0; j < len(nums); j++ {
			if i == j {
				continue
			}
			for k := 0; k < len(nums); k++ {
				if j == k || i == k {
					continue
				}
				if nums[i]+nums[j]+nums[k] == 0 {
					x := []int{nums[i], nums[j], nums[k]}
					sort.Ints(x)
					result = append(result, x)
				}
			}
		}
	}
	return removeDuplicates(result)
}

func removeDuplicates(slices [][]int) [][]int {
	seen := make(map[string]bool)
	var result [][]int

	for _, slice := range slices {
		// 将子切片转换为字符串作为map的键
		key := fmt.Sprint(slice)
		if !seen[key] {
			seen[key] = true
			result = append(result, slice)
		}
	}
	return result
}

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

暴力解法2

使用优化后的3重循环暴力解法

package main

import (
	"fmt"
	"sort"
)

// 使用3重for循环
func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	result := make([][]int, 0)
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			for k := j + 1; k < len(nums); k++ {
				if nums[i]+nums[j]+nums[k] == 0 {
					result = append(result, []int{nums[i], nums[j], nums[k]})
				}
			}
		}
	}
	return removeDuplicates(result)
}

func removeDuplicates(slices [][]int) [][]int {
	seen := make(map[string]bool)
	var result [][]int

	for _, slice := range slices {
		// 将子切片转换为字符串作为map的键
		key := fmt.Sprint(slice)
		if !seen[key] {
			seen[key] = true
			result = append(result, slice)
		}
	}
	return result
}

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

排序+双指针算法

• 首先对数组进行排序，排序后固定一个数 nums[i]，再使用左右指针指向 nums[i]后面的两端，数字分别为 nums[L] 和 nums[R]，计算三个数的和 sum 判断是否满足为 0，满足则添加进结果集

• 如果 nums[i]大于 0，则三数之和必然无法等于 0，结束循环

• 如果 nums[i] == nums[i−1]，则说明该数字重复，会导致结果重复，所以应该跳过

• 当 sum == 0 时，nums[L] == nums[L+1] 则会导致结果重复，应该跳过，L++

• 当 sum == 0 时，nums[R] == nums[R−1] 则会导致结果重复，应该跳过，R−−

• 当 sum < 0 时，L++

• 当 sum > 0 时，R–

双指针的左右指针移动条件。

核心思想：排序、双指针移动、跳过重复元素。

跳过重复元素:对于i,在遍历过程中，如果当前元素与前一个元素相同，则跳过它。

对于L,如果当前元素与后一个元素(L+1)相同，则跳过它。

对于R,如果当前元素与前一个元素(R-1)相同，则跳过它。

func threeSum(nums []int) [][]int {
	if len(nums) < 3 {
		return nil
	}
	sort.Ints(nums)
	result := make([][]int, 0)
	for i := 0; i < len(nums); i++ {
		if nums[i] > 0 {
			break
		}
		if i > 0 && nums[i] == nums[i-1] {
			continue // i去重
		}
		L := i + 1
		R := len(nums) - 1
		for L < R {
			sum := nums[i] + nums[L] + nums[R]
			if sum == 0 {
				result = append(result, []int{nums[i], nums[L], nums[R]})
				for L < R && nums[L] == nums[L+1] {
					L++ // L去重
				}
				for L < R && nums[R] == nums[R-1] {
					R-- // R去重
				}
				L++
				R--
			} else if sum < 0 {
				L++
			} else if sum > 0 {
				R--
			}
		}

	}
	return result
}