网站介绍ppt怎么做,网页制作模板左右结构,怎么建造个人网站,客户又找不到你描述
给出一个有n个元素的数组S#xff0c;S中是否有元素a,b,c满足abc0#xff1f;找出数组S中所有满足条件的三元组。 数据范围#xff1a;0 \le n \le 10000≤n≤1000#xff0c;数组中各个元素值满足 |val | \le 100∣val∣≤100
空间复杂度#xff1a;O(n^2)O(n2)S中是否有元素a,b,c满足abc0找出数组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:vectorvectorint threeSum(vectorint num) {int n num.size();mapint, vectorint mp; for(int i 0; in; i) {mp[num[i]].push_back(i);}vectorvectorint ans;for(int i 0; in; i) {for(int j i1; jn; j) {int t -(num[i] num[j]);if(mp[t].size() 0) {for(auto x : mp[t]) {if(x ! i x ! j) {ans.push_back(vectorint{num[i],num[j],num[x]});}}}}}for(int i 0; ians.size(); i) {sort(ans[i].begin(), ans[i].end());}sort(ans.begin(), ans.end());auto it unique(ans.begin(), ans.end());ans.erase(it, ans.end());return ans;}
};
