首页 > 代码库 > LeetCode "4Sum"
LeetCode "4Sum"
Similar strategy could be applied to 4Sum, as 2sum to 3sum, but that‘ll be O(n^3). Instead of 3 + 1, we can also divide it into 2 + 2. So the problem becomes finding another pair - yes hashmap.
class Solution {public: struct Rec { Rec() : i0(0), i1(0) {} Rec(int ri0, int ri1) : i0(ri0), i1(ri1) {} bool equals(Rec &r) { return i0 == r.i0 || i1 == r.i1 || i0 == r.i1 || i1 == r.i0; } int i0; int i1; }; vector<vector<int>> fourSum(vector<int> &num, int target) { vector<vector<int>> ret; if(num.size() < 4) return ret;
// Make pair size_t cnt = num.size(); unordered_map<int, vector<Rec>> hm; for (size_t i = 0; i < cnt - 1; i ++) for (size_t j = i + 1; j < cnt; j++) { int sum2 = num[i] + num[j]; if (hm.find(sum2) == hm.end()) { vector<Rec> v; v.push_back(Rec(i, j)); hm.insert(make_pair(sum2, v)); } else { hm[sum2].push_back(Rec(i, j)); } } // Match unordered_set<string> done; auto it = hm.begin(); for (; it != hm.end(); it++) { int sum1 = it->first; auto it2 = hm.find(target - sum1); if (it2 != hm.end()) { for (int i = 0; i < it2->second.size(); i ++) for (int j = 0; j < it->second.size(); j ++) { Rec &r1 = it->second[j]; Rec &r2 = it2->second[i]; if (!r1.equals(r2)) { vector<int> cv; cv.push_back(num[r1.i0]); cv.push_back(num[r1.i1]); cv.push_back(num[r2.i0]); cv.push_back(num[r2.i1]); std::sort(cv.begin(), cv.end()); string str; for (int i = 0; i < cv.size(); i++) { str += std::to_string(cv[i]); } if (done.find(str) == done.end()) { ret.push_back(cv); done.insert(str); } } } } } return ret; }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。