题目大意：给你一个数组，让你找出3个数的和为0的所有组合。
Problem:
https://leetcode.com/problems/3sum/description/
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.
|
1 2 3 4 5 6 7 |
For example, given array S = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ] |
Solution 1: Hashtable
Time complexity: O(n^2)
Space complexity: O(n)
|
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 |
// Author: Huahua class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(begin(nums), end(nums)); const int n = nums.size(); unordered_map<int, int> c; for (int x : nums) ++c[x]; vector<vector<int>> ans; for (int i = 0; i < n; ++i) { if (i && nums[i] == nums[i - 1]) continue; for (int j = i + 1; j < n; ++j) { if (j - 1 != i && nums[j] == nums[j - 1]) continue; const int t = 0 - nums[i] - nums[j]; // nums[i] <= nums[j] <= nums[k] if (t < nums[j]) continue; if (!c.count(t)) continue; // Make sure we have enough count if (c[t] >= 1 + (nums[i] == t) + (nums[j] == t)) ans.push_back({nums[i], nums[j], t}); } } return ans; } }; |
Solution 2: Sorting + Two pointers
Time complexity: O(nlogn + n^2)
Space complexity: O(1)
C++
|
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 |
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> ans; std::sort(nums.begin(), nums.end()); const int n = nums.size(); for (int i = 0; i < n - 2; ++i) { if (nums[i] > 0) break; if (i > 0 && nums[i] == nums[i - 1]) continue; int l = i + 1; int r = n - 1; while (l < r) { if (nums[i] + nums[l] + nums[r] == 0) { ans.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; } else if (nums[i] + nums[l] + nums[r] < 0) { ++l; } else { --r; } } } return ans; } }; |
Related Problems: