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. The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:[ [-1, 0, 1], [-1, -1, 2] ]
The tricky bit is to deal with the duplicated triplets. We could use a hash set to avoid the duplicate triplets.
Bruteforce Algorithm to Search For Every Possible triplets O(N^3)
We can first sort the numbers, and bruteforce each possible triplets in O(N^3) time. As the numbers are searched in ascending order, we might be able to skip the duplicates for the first number. We can use the first two numbers as the keys for the hash set. The third number will be determined if the first two are set.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(begin(nums), end(nums)); vector<vector<int>> r; unordered_set<string> v; for (int i = 0; i < nums.size(); ++ i) { if ((i > 0) && (nums[i] == nums[i - 1])) continue; // the first number should be different for (int j = i + 1; j < nums.size(); ++ j) { for (int k = j + 1; k < nums.size(); ++ k) { if (nums[i] + nums[j] + nums[k] == 0) { string a = std::to_string(nums[i]) + "," + std::to_string(nums[j]); if (!v.count(a)) { r.push_back({nums[i], nums[j], nums[k]}); v.insert(a); } } } } } return r; } }; |
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(begin(nums), end(nums)); vector<vector<int>> r; unordered_set<string> v; for (int i = 0; i < nums.size(); ++ i) { if ((i > 0) && (nums[i] == nums[i - 1])) continue; // the first number should be different for (int j = i + 1; j < nums.size(); ++ j) { for (int k = j + 1; k < nums.size(); ++ k) { if (nums[i] + nums[j] + nums[k] == 0) { string a = std::to_string(nums[i]) + "," + std::to_string(nums[j]); if (!v.count(a)) { r.push_back({nums[i], nums[j], nums[k]}); v.insert(a); } } } } } return r; } };
The space complexity is O(N) as we need to use a hash set.
Store the third number in hash map – Bruteforce Search Algorithm in O(N^2)
We can preprocess the numbers and store their max/last index in a hash map. Therefore, when we bruteforce the first two numbers in the triplets in O(N^2), we can locate (if any) the third number. If the index in the hash map is larger than the first two numbers’ indices, we find a match, but still need to use the hash set to avoid the duplicates.
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 | class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(begin(nums), end(nums)); vector<vector<int>> r; unordered_set<string> v; unordered_map<int, int> index; for (int i = 0; i < nums.size(); ++ i) { index[nums[i]] = { i }; } for (int i = 0; i < nums.size(); ++ i) { if ((i > 0) && (nums[i] == nums[i - 1])) continue; for (int j = i + 1; j < nums.size(); ++ j) { int t = -(nums[i] + nums[j]); if (index.find(t) != index.end()) { if (index[t] > j) { string a = std::to_string(nums[i]) + "," + std::to_string(nums[j]); if (!v.count(a)) { r.push_back({nums[i], nums[j], t}); v.insert(a); } } } } } return r; } }; |
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(begin(nums), end(nums)); vector<vector<int>> r; unordered_set<string> v; unordered_map<int, int> index; for (int i = 0; i < nums.size(); ++ i) { index[nums[i]] = { i }; } for (int i = 0; i < nums.size(); ++ i) { if ((i > 0) && (nums[i] == nums[i - 1])) continue; for (int j = i + 1; j < nums.size(); ++ j) { int t = -(nums[i] + nums[j]); if (index.find(t) != index.end()) { if (index[t] > j) { string a = std::to_string(nums[i]) + "," + std::to_string(nums[j]); if (!v.count(a)) { r.push_back({nums[i], nums[j], t}); v.insert(a); } } } } } return r; } };
The space complexity is O(N), as we need a hash set and a hash map.
Two Pointer Algorithm in O(N^2)
As the numbers are sorted, if we use O(N) to determine the first number, then in the sub-array, we can use two pointer algorithm to locate the second the third number with O(N). Overall, the two pointer algorithm as implemented in below C++ runs at O(N^2) complexiy – however, it is practically faster than the above O(N^2) solution – as we do not require a hash set to avoid duplicates, rather, we can just move forward the pointers if the sum stays the same.
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) { sort(begin(nums), end(nums)); vector<vector<int>> r; for (int i = 0; i < nums.size(); ++ i) { if ((i > 0) && (nums[i] == nums[i - 1])) continue; int j = i + 1; int k = nums.size() - 1; while (j < k) { if (nums[i] + nums[j] + nums[k] == 0) { r.push_back({nums[i], nums[j], nums[k]}); while ((j < k) && nums[j] == nums[j + 1]) j ++; // skip duplicates while ((j < k) && nums[k] == nums[k - 1]) k --; // skip duplicates j ++; k --; } else if (nums[i] + nums[j] + nums[k] > 0) { k --; } else { j ++; } } } return r; } }; |
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(begin(nums), end(nums)); vector<vector<int>> r; for (int i = 0; i < nums.size(); ++ i) { if ((i > 0) && (nums[i] == nums[i - 1])) continue; int j = i + 1; int k = nums.size() - 1; while (j < k) { if (nums[i] + nums[j] + nums[k] == 0) { r.push_back({nums[i], nums[j], nums[k]}); while ((j < k) && nums[j] == nums[j + 1]) j ++; // skip duplicates while ((j < k) && nums[k] == nums[k - 1]) k --; // skip duplicates j ++; k --; } else if (nums[i] + nums[j] + nums[k] > 0) { k --; } else { j ++; } } } return r; } };
The Two Pointer implementation uses O(1) constant space.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: How to Trim a Binary Search Tree using Depth First Search Algorithm (Recursion)?
Next Post: WordPress Membership Plugin
In the second and first approach you don’t need an unordered_set. Since the elements are sorted, you can simply check the previous element and if it is repeated continue. Exactly as you did with nums[i].
Thanks, you are right. Good catch!
Thank you for your sharing and I finally made an accepted solution base on yours.
You ‘re welcome!