{"id":4052,"date":"2018-09-19T23:27:38","date_gmt":"2018-09-20T06:27:38","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4052"},"modified":"2018-09-19T23:36:52","modified_gmt":"2018-09-20T06:36:52","slug":"leetcode-18-4sum","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/binary-search\/leetcode-18-4sum\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 18. 4Sum"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

Given an array\u00a0nums<\/code>\u00a0of\u00a0n<\/em>\u00a0integers and an integer\u00a0target<\/code>, are there elements\u00a0a<\/em>,\u00a0b<\/em>,\u00a0c<\/em>, and\u00a0d<\/em>\u00a0in\u00a0nums<\/code>\u00a0such that\u00a0a<\/em>\u00a0+\u00a0b<\/em>\u00a0+\u00a0c<\/em>\u00a0+\u00a0d<\/em>\u00a0=\u00a0target<\/code>? Find all unique quadruplets in the array which gives the sum of\u00a0target<\/code>.<\/p>\n

Note:<\/strong><\/p>\n

The solution set must not contain duplicate quadruplets.<\/p>\n

Example:<\/strong><\/p>\n

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.\r\n\r\nA solution set is:\r\n[\r\n  [-1,  0, 0, 1],\r\n  [-2, -1, 1, 2],\r\n  [-2,  0, 0, 2]\r\n]<\/pre>\n
Solution 1: Sorting + Binary Search<\/strong><\/h1>\n
Time complexity: O(n^3 log n + klogk)<\/p>\n
Space complexity: O(k)<\/p>\n
\n
C++<\/h2>\n
\n\n
\/\/ Author: Huahua\r\nclass Solution {\r\npublic:\r\n  vector<vector<int>> fourSum(vector<int> &num, int target) {\r\n    set<vector<int>> h; \r\n\r\n    sort(num.begin(), num.end());\r\n\r\n    int n = num.size();\r\n\r\n    for (int i = 0; i < n; i++) {\r\n      for (int j = i + 1; j < n; j++) {\r\n        for(int k = j + 1; k < n; k++) {\r\n          int t = target - num[i] - num[j] - num[k];\r\n          if (t < num[k]) break;\r\n          if (!std::binary_search(num.begin() + k + 1, num.end(), t)) continue;          \r\n          h.insert({num[i], num[j], num[k], t});          \r\n        }\r\n      }\r\n    }\r\n    return vector<vector<int>>(begin(h), end(h));\r\n  }\r\n};<\/pre>\n\n<\/div>
C++ opt<\/h2>\n
\n\n
\/\/ Author: Huahua\r\nclass Solution {\r\npublic:\r\n  vector<vector<int>> fourSum(vector<int> &num, int target) {        \r\n    sort(num.begin(), num.end());\r\n    if (target > 0 && target > 4 * num.back()) return {};\r\n    if (target < 0 && target < 4 * num.front()) return {};\r\n    \r\n    set<vector<int>> h;    \r\n    int n = num.size();\r\n\r\n    for (int i = 0; i < n; i++) {   \r\n      for (int j = i + 1; j < n; j++) {                \r\n        for(int k = j + 1; k < n; k++) {\r\n          int t = target - num[i] - num[j] - num[k];\r\n          if (t < num[k]) break;\r\n          if (!std::binary_search(num.begin() + k + 1, num.end(), t)) continue;          \r\n          h.insert({num[i], num[j], num[k], t});          \r\n        }           \r\n      }\r\n    }\r\n\r\n    return vector<vector<int>>(begin(h), end(h));\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n
Solution 2: Sorting + HashTable<\/strong><\/h1>\n
Time complexity: O(n^3 + klogk)<\/p>\n
Space complexity: O(n + k)<\/p>\n
\n
C++<\/h2>\n
\n\n
\/\/ Author: Huahua\r\nclass Solution {\r\npublic:\r\n  vector<vector<int>> fourSum(vector<int> &num, int target) {        \r\n    sort(num.begin(), num.end());\r\n    if (target > 0 && target > 4 * num.back()) return {};\r\n    if (target < 0 && target < 4 * num.front()) return {};\r\n    \r\n    unordered_map<int, int> index;\r\n    for (int i = 0; i < num.size(); ++i)\r\n      index[num[i]] = i;\r\n    \r\n    set<vector<int>> h;    \r\n    int n = num.size();\r\n\r\n    for (int i = 0; i < n; i++) {   \r\n      for (int j = i + 1; j < n; j++) {                \r\n        for(int k = j + 1; k < n; k++) {\r\n          int t = target - num[i] - num[j] - num[k];\r\n          if (t < num[k]) break;\r\n          auto it = index.find(t);\r\n          if (it == index.end() || it->second <= k) continue;\r\n          h.insert({num[i], num[j], num[k], t});\r\n        }           \r\n      }\r\n    }\r\n\r\n    return vector<vector<int>>(begin(h), end(h));\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n
Related Problems<\/strong><\/h1>\n