15 - 三数之和
problem description
给定一个包含 n 个整数的数组? nums, 判断? nums? 中是否存在三个元素 a,b,c , 使得? a + b + c = 0 ? 找出所有满足条件且不重复的三元组.
注意: 答案中不可以包含重复的三元组.
- thinking
- Feel tired for timeout issue. :-(
- code
- class Solution {
- public:
- vector<vector<int>> threeSum(vector<int>& nums) {
- int target;
- vector<vector<int>> ans;
- sort(nums.begin(), nums.end());
- for (int i = 0; i <nums.size(); i++) {
- if (i> 0 && nums[i] == nums[i - 1]) continue;
- if ((target = nums[i])> 0) break;
- int l = i + 1, r = nums.size() - 1;
- while (l <r) {
- if (nums[l] + nums[r] + target < 0) ++l;
- else if (nums[l] + nums[r] + target> 0) --r;
- else {
- ans.push_back({target, nums[l], nums[r]});
- ++l, --r;
- while (l < r && nums[l] == nums[l - 1]) ++l;
- while (l < r && nums[r] == nums[r + 1]) --r;
- }
- }
- }
- return ans;
- }
- };
来源: http://www.bubuko.com/infodetail-3354889.html