首页 > 代码库 > 3Sum
3Sum
Given an array S of n integers, are there elements a, b, c in S 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.
For example, given array S = [-1, 0, 1, 2, -1, -4],A solution set is:[ [-1, 0, 1], [-1, -1, 2]]
class Solution{public: vector<vector<int>> threeSum(vector<int> & nums){ vector<vector<int>> res; if(nums.size() < 3) return res; sort(nums.begin(),nums.end()); for(size_t i=0;i<nums.size();i++){ int target = -nums[i]; int front = i + 1; int back = nums.size()-1; while(front < back){ if(nums[front] + nums[back] < target) front++; else if(nums[front] + nums[back] > target) back--; else{ res.push_back({nums[i],nums[front],nums[back]}); while(front < back && res.back()[1]==nums[front]) front++; while(front < back && res.back()[2]==nums[back]) back--; } } while(i+1 < nums.size() && nums[i+1] == nums[i]) i++; } return res; }};
3Sum
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。