2021-09-01:三数之和。给你一个包含 n 个整数的数组 nums,判断 num

2021-09-01:三数之和。给你一个包含 n 个整数的数组 nums,判断 num

佘征楠 2024-11-19 百科资讯 473 次浏览 0个评论

2021-09-01:三数之和。给你一个包含 n 个整数的数组 nums,判断 num

问题描述

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

2021-09-01:三数之和。给你一个包含 n 个整数的数组 nums,判断 num

算法思路

这是一个经典的三数之和问题。我们可以采用类似于两数之和的解法,通过双指针的方式来解决。

首先,对数组进行排序。然后,使用三个指针,分别指向数组的起始位置、当前遍历位置和末尾位置。遍历数组时,我们固定一个数,然后使用双指针来寻找其余两个数。

代码实现

以下是使用Go语言实现的代码:

package main

import (
 "fmt"
 "sort"
)

func threeSum(nums []int) [][]int {
 sort.Ints(nums)
 N := len(nums)
 ans := make([][]int, 0)

 for i := 0; i < N-2; i++ {
 if i > 0 && nums[i] == nums[i-1] {
 continue
 }

 left := i + 1
 right := N - 1

 for left < right {
 sum := nums[i] + nums[left] + nums[right]

 if sum == 0 {
 ans = append(ans, []int{nums[i], nums[left], nums[right]})

 for left < right && nums[left] == nums[left+1] {
 left++
 }
 for left < right && nums[right] == nums[right-1] {
 right--
 }
 left++
 right--
 } else if sum < 0 {
 left++
 } else {
 right--
 }
 }
 }

 return ans
}

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

执行结果

数组元素 0 1 2 -1 -1 -4
结果 -1 -1 2 0 1 4

如上所示,程序输出了所有和为0的三元组。

转载请注明来自易保微信测试平台,本文标题:《2021-09-01:三数之和。给你一个包含 n 个整数的数组 nums,判断 num 》

百度分享代码,如果开启HTTPS请参考李洋个人博客
每一天,每一秒,你所做的决定都会改变你的人生!
Top