这道题蛮有意思的,本以为需要很多奇特的思路,结果按照自己的思路写了一下代码,简单的优化一下,最终通过了。所以说,很多时候就是干,然后就有结果了。
三数之和
给你一个包含 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
解题思路
代码位置:https://github.com/shidawuhen/asap/blob/master/controller/algorithm/15-3sum.go
数组排序后,选取两个数值,剩下的数据从map中选择,如果有对应值,则判断是否已经存在,如果不存在则记录,否则不记录。
这个方案导致超时,所以需要进一步优化。如果三个数据的和为0,则至少有一个为负值,一个为正值,所以遍历的时候,第一层遍历,只需要遍历到正值开始之前即可。
另外,只能说Go的执行效率够高。
代码
反正我过了:
1 | func threeSum(nums []int) [][]int { |