【NC54 三数之和】（待整理）

【NC54 三数之和】（待整理）

描述

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

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

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

注意：

三元组（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]]

解题报告：

看了题解发现可以用双指针，抽空补上。

我这道题是最后再去重的，注意这题不可以先对所有数字排序然后上来就去重。比如[-4,2,2].

AC代码：

class Solution {public: vector > threeSum(vector &num) { int n = num.size(); map> mp; for(int i = 0; i > ans; for(int i = 0; i 0) { for(auto x : mp[t]) { if(x != i &&x != j) { ans.push_back(vector{num[i],num[j],num[x]}); } } } } } for(int i = 0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。