题面
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
样例
1 2
| 输入:nums = [-1, 0, 1, 2, -1, 4] 输出:ans = [[-1, 0, 1], [-1, -1, 2]]
|
思路
排序+双指针+vector数组去重,去重有两种方式🙂
vector + set去重
set<vector<int>> s(ans.begin(), ans.end());
ans.assign(s.begin(), s.end());
过是可以过,但是….
第二种就是在代码里面去重,如果碰到重复的就跳过,这个不算太差..
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| vector<vector<int>> threeSum(vector<int>& nums) { int n = nums.size(); if(nums.size() < 3) return {}; sort(nums.begin(), nums.end());
vector<vector<int>> ans; for(int i = 0; i < n - 2 && nums[i] <= 0; i++) { int l = i + 1, r = n - 1; if(i > 0 && nums[i] == nums[i - 1]) continue; while(l < r) { int tmp = nums[i] + nums[l] + nums[r]; if(tmp > 0) r--; else if(tmp < 0) l++; else { while(l < r && nums[l] == nums[l + 1]) l++; while(l < r && nums[r] == nums[r - 1]) r--; ans.push_back({nums[i], nums[l], nums[r]}); l++; r--; } } } return ans; }
|