首页 > 代码库 > leetcode. 4Sum
leetcode. 4Sum
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:
- Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
- 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)
与3sum类似，逐渐递减到2sum。1 vector<vector<int> > fourSum(vector<int> &num, int target) 2 { 3 int k = 0, l = 0; 4 int sum = 0; 5 vector<int> t(4); 6 vector<vector<int> > vt; 7 if (num.size() < 4) 8 return vt; 9 10 sort(num.begin(), num.end());11 for (int i = 0; i < num.size() - 3; i++)12 {13 if (i > 0 && num[i] == num[i - 1])14 continue;15 for (int j = i + 1; j < num.size() - 2; j++)16 {17 if ((j > i + 1) && (num[j] == num[j - 1]))18 continue;19 k = j + 1;20 l = num.size() - 1;21 while (k < l)22 {23 if ((k > j + 1) && (num[k] == num[k - 1]))24 {25 k++;26 continue;27 }28 if ((l < num.size() - 1) && (num[l] == num[l + 1]))29 {30 l--;31 continue;32 }33 sum = num[i] + num[j] + num[k] + num[l];34 if (sum == target)35 {36 t.clear();37 t.push_back(num[i]);38 t.push_back(num[j]);39 t.push_back(num[k]);40 t.push_back(num[l]);41 vt.push_back(t);42 k++;43 l--;44 }45 else if (sum < target)46 k++;47 else48 l--;49 }50 }51 }52 53 return vt;54 }
时间复杂度：O(n^3)
leetcode. 4Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。