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:
参考链接: https://leetcode-cn.com/problems/3sum/solution/three-sum-ti-jie-by-wonderful611/
解法：双指针
链接里说的很详细，注意去重复
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(),nums.end()); vector<vector<int>> ans; if(nums.empty() || nums.front()>0 || nums.back()<0) return {}; for(int i=0;i<nums.size()-1;i++) { if(i>0 && nums[i-1]==nums[i])continue; int l=i+1,r=nums.size()-1; while(l<r) { if(nums[i]+nums[l]+nums[r]>0) { while(l<r && nums[r-1]==nums[r])r--; r--; } else if(nums[i]+nums[l]+nums[r]<0) { while(l<r&& nums[l+1]==nums[l])l++; l++; } else{ ans.push_back(vector<int>{nums[i],nums[l],nums[r]}); while(l<r && nums[r-1]==nums[r])r--; while(l<r&& nums[l+1]==nums[l])l++; r--; l++; } } } return ans; } };
近期评论