我要招人

去企业版

首页 > 试题广场 >

三数之和

[编程题]三数之和

热度指数：224055 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。

数据范围： $0 \le n \le 1000$ ，数组中各个元素值满足 $|val | \le 100$

空间复杂度： $O(n^2)$ ，时间复杂度 $O(n^2)$

注意：

三元组（a、b、c）中的元素必须按非降序排列。（即a≤b≤c）
解集中不能包含重复的三元组。

例如，给定的数组 S = {-10 0 10 20 -10 -40},解集为(-10, -10, 20),(-10, 0, 10)

示例1

输入

[0]

输出

[]

示例2

输入

[-2,0,1,1,2]

输出

[[-2,0,2],[-2,1,1]]

示例3

输入

[-10,0,10,20,-10,-40]

输出

[[-10,-10,20],[-10,0,10]]

算法知识视频讲解

2019113913

发表于 2021-07-09 14:29:13

精华题解题意思路：找出三个数相加为0的组合，即a+b+c=0，题目输出为三元组（a、b、c）中的元素必须按非降序排列。（即a≤b≤c）。方法一：暴力法首先最朴素的做法是先排序然后通过三重循环寻找答案,可以优化如果循环的当前数和之前一样则continue，可以卡过本题数据。时间复杂度：O(nlogn) + 展开全文

牛客题解官

发表于 2022-04-22 12:27:37

精华题解题目主要信息: 给定一个长度为nnn的数组，要找出其中所有满足相加等于0的三元组，即数组中所有三个相加为0的数集三元组内部必须非降序排列，且三元组不能有重复举一反三：学习完本题的思路你可以解决如下题目： BM50. 两数之和哈希表（推荐使用）知识点1：哈希表哈希表是一种根据关键码（k 展开全文

堆栈哲学

发表于 2021-07-14 12:10:37

精华题解解法一：双指针对数组长度进行特判排序 num[i]>0说明后面的三数和不可能等于0。对于重复元素跳过左指针left=i+1，右指针right = len-1 当nums[i]+nums[left]+nums[right]==0执行循环，判断左界和右界是否和下一位置重复，去除重复解展开全文

Maokt

发表于 2021-07-13 11:50:26

精华题解算法思想一：双指针解题思路算法流程： 1、特判，对于数组长度 n，如果数组为 null 或者数组长度小于 3，返回 []。 2、对数组进行排序。 3、遍历排序后数组： 1、若 num[i]>0：因为已经排序好，所以后面不可能展开全文

未来0116

发表于 2021-07-14 11:06:49

精华题解一.题目描述题目链接:https://www.nowcoder.com/practice/345e2ed5f81d4017bbb8cc6055b0b711?tpId=196&&tqId=37085&rp=1&ru=/activity/oj&qru=/ta/jo 展开全文

LifelongCode

发表于 2021-01-21 20:00:42

思路：（1）首先对数组进行排序（从小到大）（2）依次取出第 i 个数（i从0开始），并且不重复的选取（跳过重复的数）（3）这样问题就转换为 2 个数求和的问题（可以用双指针解决方法）==》数求和问题（4）定义两个指针：左指针（left）和右指针（right）（5）找出固定 left，此时lef 展开全文

华科不平凡

发表于 2020-08-16 01:36:04

先排序，然后以第一个值为基准开始遍历，用双指针求第二个值和第三个值。 class Solution { public: vector<vector<int> > threeSum(vector<int> &num) { sort(n 展开全文

honokawings

发表于 2022-03-20 09:49:18

* * @param num int整型一维数组 * @param numLen int num数组长度 * @return int整型二维数组 * @return int* returnSize 返回数组行数 * @return int** returnColumnSizes 返回数展开全文

执子一白

发表于 2020-12-08 10:35:15

考虑输出需要，这里直接排序同时方便计算注意去重问题 import java.util.*; public class Solution { public ArrayList<ArrayList<Integer>> threeSum(int[] num) { 展开全文

Auto~

发表于 2021-04-01 17:32:32

(1)由于a<=b<=c 使用排序,将数组从下到大排序,这样递归的结果永远都是啊a<=b<=c;(2)递归+回溯+剪支 class Solution { public: void gen(int i,set<vector<int>> & 展开全文

数据结构和算法

发表于 2021-04-13 10:48:05

先对数组排序，然后固定一个数字，再求两个数字之和。 public ArrayList<arraylist<integer>> threeSum(int[] num) { //先排序 Arrays.sort(num); A 展开全文

生来逆旅单行道

发表于 2021-05-08 18:21:47

超级详细的题解与代码备注：（C++代码）思路：首先判断给点数组的大小是否<3 小于3的话则直接返回一个空的结果.对整个数组进行排序:寻找一个基准值target（基准值为从数组的第1个元素到倒数第三个元素），然后再从基准值target的后面找到两个数组等于-target，这个时候是不是就是求展开全文

Shauby

发表于 2022-08-09 17:59:53

将三数和，转换成n个两数和问题求解。时间O(n^2)，空间O(n)。以排序后的元组作为集合元素，自带去重效果。用取值的剩余次数来避免重复取值，和避免多次出现的值的漏选。 class Solution: def 展开全文

Mr__Nobody

发表于 2021-09-23 11:22:48

# # # @param num int整型一维数组 # @return int整型二维数组 # class Solution: def threeSum(self , num ): # write code here length = len(num) 展开全文

讲道理的豹子说这不是bug

发表于 2023-08-05 12:39:37

方法：双指针+排序具体步骤：对数组进行排序，便于后续的查找遍历数组，得到第一个数字后，将问题转换为寻找两个数字之和为第一个数字相反数的问题其中要注意重复的数字要去除。时间复杂度：o(n2)。排序需要o(logn)，遍历需要o(n2)。空间复杂度：o(1) class Solution { p 展开全文

问题信息

数组双指针排序

来自：经典编程练习-难题卷

难度：

342条回答 1365收藏 31302浏览

通过挑战的用户

查看代码

牛客30382...

2022-12-24 21:11:53
Jack100...

2022-11-24 01:25:30
菜鸟鸟2024

2022-11-15 22:40:19
牛客89418...

2022-10-27 16:51:43
牛客31924...

2022-10-21 23:21:57

三数之和

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题