15. 3Sum
题目描述
- Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
- Note:
The solution set must not contain duplicate triplets.
- Example:
- Given array nums = [-1, 0, 1, 2, -1, -4],
- A solution set is:
- [
- [-1, 0, 1],
- [-1, -1, 2]
- ]
给出一个有 n 个元素的数组 S,S 中是否有元素 a,b,c 满足 a+b+c=0? 找出数组 S 中所有满足条件的三元组.
注意:
三元组 (a,b,c,d) 中的元素必须按非降序排列.(即 a≤b≤c)
解集中不能包含重复的三元组.
例如, 给定的数组 S = {-1 0 1 2 -1 -4}, 解集为: (-1, 0, 1) (-1, -1, 2)
思路分析
暴力解决法是每个人都能想到的, 三层 for 循环, 时间复杂度是 O(n^3), 而且还要处理重复的问题, 显然不是题目想要的解法.
那能不能降到 O(n^2)? 排序算法的时间复杂度为 O(nlgn), 小于 O(n^2), 那么我们不妨先对数组排个序.
排序之后, 我们就可以对数组用两个指针分别从前后两端向中间扫描了, 如果是 2Sum, 我们找到两个指针之和为 target 就 OK 了, 那 3Sum 类似, 我们可以先固定一个数, 然后找另外两个数之和为第一个数的相反数就可以了.
要我们找出三个数且和为 0, 那么除了三个数全是 0 的情况之外, 肯定会有负数和正数, 我们还是要先确定一个数, 然后去找另外两个数, 我们只要找到两个数且和为第一个确定数的相反数就行了.
我们对原数组进行排序, 然后开始遍历排序后的数组, 这里注意不是遍历到最后一个停止, 而是到倒数第三个就可以了.
对于遍历到的数, 用 0 减去这个确定的数得到一个 target, 然后只需要再之后找到两个数之和等于 target 即可. 我们用两个指针分别指向 fix 数字之后开始的数组首尾两个数, 如果两个数和正好为 target, 则将这两个数和 fix 的数一起存入结果中. 然后就是跳过重复数字的步骤了, 两个指针都需要检测重复数字. 如果两数之和小于 target, 则我们将左边那个指针 i 右移一位, 使得指向的数字增大一些. 同理, 如果两数之和大于 target, 则我们将右边那个指针 j 左移一位, 使得指向的数字减小一些.
由于不能有重复的三元组, 因此若等于 target 后, 需要对 l 和 r 都作重复判断.
- class Solution {
- public:
- vector<vector<int>> threeSum(vector<int> &num) {
- vector<vector<int>> res;
- sort(num.begin(),num.end());
- int n = num.size();
- for(int i=0;i<n;++i)
- {
- if(num[i]>0)
- break;
- if(i>0&&num[i]==num[i-1])
- continue;
- int t = 0-num[i];
- int l=i+1,r=n-1;
- while(l<r)
- {
- if(num[l]+num[r]==t)
- {
- res.push_back({num[i],num[l],num[r]});
- while(l<r&&num[l]==num[l+1]) l++;
- while(l<r&&num[r]==num[r-1]) r--;
- l++;r--;
- }
- else if(num[l]+num[r]<t)
- l++;
- else
- r--;
- }
- }
- return res;
- }
- };
来源: http://www.bubuko.com/infodetail-3519351.html