我要招人

去企业版

首页 > 试题广场 >

三数之和

[编程题]三数之和

热度指数：221664 时间限制：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，这个时候是不是就是求展开全文

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) 展开全文

哥德巴赫草稿纸上的0

发表于 2022-08-22 10:56:05

class Solution: def threeSum(self , num) : num=sorted 展开全文

馒头2020

发表于 2021-04-07 15:58:26

题目描述描述转载自力扣《15. 三数之和》给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。示例1 输入：nums = [-1,0,1,2 展开全文

问题信息

数组双指针排序

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

难度：

341条回答 1335收藏 29451浏览

通过挑战的用户

牛客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

三数之和

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题