Problem
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
The solution set must not contain duplicate quadruplets.
Example:
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0. A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
Solution 1: Sorting + Binary Search
Time complexity: O(n^3 log n + klogk)
Space complexity: O(k)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua class Solution { public: vector<vector<int>> fourSum(vector<int> &num, int target) { set<vector<int>> h; sort(num.begin(), num.end()); int n = num.size(); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for(int k = j + 1; k < n; k++) { int t = target - num[i] - num[j] - num[k]; if (t < num[k]) break; if (!std::binary_search(num.begin() + k + 1, num.end(), t)) continue; h.insert({num[i], num[j], num[k], t}); } } } return vector<vector<int>>(begin(h), end(h)); } }; |
C++ opt
|
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>> fourSum(vector<int> &num, int target) { sort(num.begin(), num.end()); if (target > 0 && target > 4 * num.back()) return {}; if (target < 0 && target < 4 * num.front()) return {}; set<vector<int>> h; int n = num.size(); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for(int k = j + 1; k < n; k++) { int t = target - num[i] - num[j] - num[k]; if (t < num[k]) break; if (!std::binary_search(num.begin() + k + 1, num.end(), t)) continue; h.insert({num[i], num[j], num[k], t}); } } } return vector<vector<int>>(begin(h), end(h)); } }; |
Solution 2: Sorting + HashTable
Time complexity: O(n^3 + klogk)
Space complexity: O(n + k)
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 27 28 29 30 |
// Author: Huahua class Solution { public: vector<vector<int>> fourSum(vector<int> &num, int target) { sort(num.begin(), num.end()); if (target > 0 && target > 4 * num.back()) return {}; if (target < 0 && target < 4 * num.front()) return {}; unordered_map<int, int> index; for (int i = 0; i < num.size(); ++i) index[num[i]] = i; set<vector<int>> h; int n = num.size(); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for(int k = j + 1; k < n; k++) { int t = target - num[i] - num[j] - num[k]; if (t < num[k]) break; auto it = index.find(t); if (it == index.end() || it->second <= k) continue; h.insert({num[i], num[j], num[k], t}); } } } return vector<vector<int>>(begin(h), end(h)); } }; |