三数之和，去除重复。

朴灿烈づ我的快乐病毒、 2021-12-15 03:03 186阅读 0赞

给定一个包含 *n* 个整数的数组 `nums`，判断 `nums` 中是否存在三个元素 *a，b，c ，*使得 *a + b + c = *0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

思路1：仿照两数之和，不需要排序，但是会返回重复复的三元组，因此要去重，用标准库unique函数出重，仍通不过最后一个很多零的测试用例，但是还是把代码贴一下；

思路2：先排序，然后用滑动窗口法，找匹配的三元组，在数组值相同时，窗口左右游标滑动，来达到去重目的，排序复杂度nlogn，遍历两次数组，复杂度n的平方，总复杂度n的平方。

![1623979-20190313191429001-891909485.png][]

/

class Solution \{  
public:  
vector<vector<int> > threeSum(vector<int> &num) \{  
vector<vector<int> > res;

std::sort(num.begin(), num.end());

for (int i = 0; i < num.size(); i++) \{  
  
int target = -num\[i\];  
int front = i + 1;  
int back = num.size() - 1;

while (front < back) \{

int sum = num\[front\] + num\[back\];

if (sum < target)  
front++;

else if (sum > target)  
back--;

else \{  
vector<int> triplet(3, 0);  
triplet\[0\] = num\[i\];  
triplet\[1\] = num\[front\];  
triplet\[2\] = num\[back\];  
res.push\_back(triplet);

while (front < back && num\[front\] == triplet\[1\]) front++;  
while (front < back && num\[back\] == triplet\[2\]) back--;  
\}  
  
\}  
  
while (i + 1 < num.size() && num\[i + 1\] == num\[i\])  
i++;

\}  
  
return res;  
  
\}  
\};

///

转载于:https://www.cnblogs.com/zzas0/p/10525483.html

[1623979-20190313191429001-891909485.png]: /images/20211214/6c93370baf634e33b09f9b12a09d9f9a.png

发表评论取消回复

表情：

评论列表（有 0 条评论，186人围观）

还没有评论，来说两句吧...

相关阅读

相关两数之和、三数之和、四数之和、K数之和

数之和、三数之和、四数之和和K数之和是最近听室友提起的几道有意思的基础题，可以说是把双指针运用的淋漓尽致。（K数之和其实是一个动态规划的题，此处因为满足`*数之和`的的结...

淡淡的烟草味﹌/ 2024年04月17日 19:48/ 0 赞/ 97 阅读

相关三数之和

题目：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组

「爱情、让人受尽委屈。」/ 2023年10月02日 12:57/ 0 赞/ 28 阅读

相关三数之和

每日一题–三数之和今天来看一道三数之和的面试题，思路比较简单，直接看题。题目描述　　给定一个数组和一个目标值，从数组中找到三个值，使其和最接近目标值。

逃离我推掉我的手/ 2023年02月27日 10:36/ 0 赞/ 14 阅读

相关三数之和

一、前言问题来源LeetCode 问题链接：[https://leetcode-cn.com/explore/interview/card/bytedance/243

小灰灰/ 2023年02月18日 09:33/ 0 赞/ 12 阅读

相关三数之和

public class ThreeNumSum { //NC54 三数之和 https://www.nowcoder.com/practice/345e2

àì夳堔傛蜴生んèń/ 2023年01月21日 11:15/ 0 赞/ 14 阅读

相关三数之和

三数之和 1、参考资料 https://leetcode-cn.com/problems/3sum/ https://leetcode-cn.com/proble

深碍√TFBOYSˉ_/ 2022年12月03日 09:13/ 0 赞/ 142 阅读

相关【lintcode】两数之和、三数之和、最接近的三数之和、四数之和小结

两数之和给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于

不念不忘少年蓝@/ 2022年06月05日 06:53/ 0 赞/ 250 阅读

相关 leetcode 两数之和、三数之和、最接近的三数之和、四数之和

两数之和题目链接：[两数之和][Link 1] 给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重

缺乏、安全感/ 2022年05月25日 06:46/ 0 赞/ 346 阅读

相关 LeetCode 两数之和、三数之和

1. 两数之和给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的两个整数。你可以假设每种输入只会对应一个答案。但是，你不能重复

旧城等待，/ 2022年04月13日 05:42/ 0 赞/ 289 阅读

相关三数之和，去除重复。

给定一个包含 n 个整数的数组 `nums`，判断 `nums` 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。注

朴灿烈づ我的快乐病毒、/ 2021年12月15日 03:03/ 0 赞/ 187 阅读