描述 Given an array S of n integers, are there elements a, b, c, and d in S 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.
For example, given array S = [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]]分析 先排序，然后左右夾逼，復雜度 O(n3)，會超時。 可以用一個 hashmap 先緩存兩個數的和，最終復雜度 O(n3)。這個策略也適用于 3Sum 。
class Solution {public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> result; if (nums.size() < 4) return result; sort(nums.begin(), nums.end()); auto last = nums.end(); for (auto a = nums.begin(); a < PRev(last, 3); ++a) { for (auto b = next(a); b < prev(last, 2); ++b) { auto c = next(b); auto d = prev(last); while (c < d) { if (*a + *b + *c + *d < target) ++c; else if (*a + *b + *c + *d > target) --d; else { result.push_back({*a, *b, *c, *d}); ++c; --d; } } } } sort(result.begin(), result.end()); result.erase(unique(result.begin(), result.end()), result.end()); // 刪除重復項 return result; }};新聞熱點
疑難解答
