首页 > 代码库 > 【LeetCode】4Sum
【LeetCode】4Sum
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)
先确定前两个数num[i],num[j]，
然后设置双指针k,l分别指向两端，往中间扫。
(1)(sum = num[i]+num[j]+num[k]+num[l]) == taget，则找到其中一个解（注意用map去重）。k++,l--.
(2)sum > target, l--
(3)sum < target, k++
class Solution {public: vector<vector<int> > fourSum(vector<int> &num, int target) { vector<vector<int> > result; if(num.empty() || num.size() < 4) return result; int size = num.size(); sort(num.begin(), num.end()); map<vector<int>, bool> m; for(int i = 0; i < size-3; i ++) { for(int j = i+1; j < size-2; j ++) { int k = j+1; //k < size-1 int l = size-1; while(k < l) { int sum = num[i]+num[j]+num[k]+num[l]; if(sum == target) { vector<int> cur(4,0); cur[0] = num[i]; cur[1] = num[j]; cur[2] = num[k]; cur[3] = num[l]; if(m.find(cur) == m.end()) { result.push_back(cur); m[cur] = true; } k ++; l --; } else if(sum > target) l --; else k ++; } } } return result; }};
【LeetCode】4Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。