题目描述：
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.
样例：
1 2 3 4 5 6 7
Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
题意：
给你 n 个数，要找出三个不同的数相加为 0，并返回这三个数
思路：
对数组排序，然后遍历。
在遍历到正数的时候，因为数组是有序的，后面的数也全是正数，那么就永远不可能相加为 0，所以后面的数字就不需要再进行遍历。
同时，还会有重复的数值出现，所以当遍历到重复的元素的时候，就跳过。
在对于遍历到的数，用 0 减去当前遍历的数得到一个 target，然后就只需要在当前数之后找到两数之和为 target 的两个数即可。
我的代码如下：
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
class {public : vector <vector <int >> threeSum(vector <int >& nums) { vector <vector <int >> res; sort(nums.begin(), nums.end()); int n = nums.size(); if (n == 0 || nums.back() < 0 || nums.front() > 0 ) return res; for (int i = 0 ; i < n; ++i){ if (nums[i] > 0 ) break ; if (i > 0 && nums[i] == nums[i - 1 ]) continue ; int target = 0 - nums[i]; int l = i + 1 , r = nums.size() - 1 ; while (l < r){ if (nums[l] + nums[r] == target){ res.push_back({nums[i], nums[l], nums[r]}); while (l < r && nums[l] == nums[l + 1 ]) ++l; while (l < r && nums[r] == nums[r - 1 ]) --r; ++l; --r; } else if (nums[l] + nums[r] > target) --r; else ++l; } } return res; } };
Runtime：112ms Memory：16.2MB
近期评论