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:
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 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ， 使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意： 答案中不可以包含重复的三元组。
1 2 3 4 5 6 7 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
想法 思路就是固定一个值然后寻找其他两个值的和与第一个值互为相反数即可。对于乱序数组来说只能通过遍历来找和，那么复杂度是$O(n^2)$，因此可以先排序再用双指针（头和尾各一个）查找，复杂度是$O(n \log{n})$。对于双指针来说，如果$(b+c) > -a$ 说明$c$过大，右指针左移；如果$(b+c) < -a$说明$b$过小，左指针右移。
解 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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 #include <algorithm> #include <iostream> #include <vector> using namespace std ;class Solution { public : vector <vector <int >> threeSum(vector <int > &nums) { vector <vector <int >> ans; sort(nums.begin(), nums.end()); if (nums.size() < 3 ) { return ans; } for (int i = 0 ; i < nums.size() - 2 ; i++) { if (i == 0 || i > 0 && nums[i] != nums[i - 1 ]) { int left = i + 1 , right = nums.size() - 1 , sum = -nums[i]; while (left < right) { if (nums[left] + nums[right] == sum) { ans.push_back(vector <int >({nums[i], nums[left], nums[right]})); while (left < right && nums[left] == nums[left + 1 ]) { left++; } while (left < right && nums[right] == nums[right - 1 ]) { right--; } left++; right--; } else if (nums[left] + nums[right] < sum) { left++; } else { right--; } } } } return ans; } }; int main (void ) Solution s; vector <int > m = {-1 , 0 , 1 }; for (auto v : s.threeSum(m)) { for (auto i : v) { cout << i << ' ' ; } cout << endl ; }; return 0 ; }
