LeetCode 题解（17）: 4Sum

本文主要是介绍LeetCode 题解（17）: 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)

题解：

先对数组排序，利用STL set 解决了重复 quadruplet 问题, 再把4sum分解为 1个元素+3Sum，再进一步分解为 1个元素 + 另1个元素 + 2Sum，再利用2Sum求解。336ms过。

class Solution {
public:vector<vector<int>> fourSum(vector<int> &num, int target) {vector<vector<int>> results;if(num.size() < 4)return results;sort(num.begin(), num.end());set<vector<int>> result;for(int i = 0; i < num.size() - 3; i++){int sum = target - num[i];for(int j = i + 1; j < num.size() - 2; j++){sum -= num[j];//2-sum hereint start = j + 1;int end = num.size() - 1;while(start < end){if(num[start] + num[end] == sum){vector<int> temp;temp.push_back(num[i]);temp.push_back(num[j]);temp.push_back(num[start]);temp.push_back(num[end]);result.insert(temp);start++;end--;}else if(num[start] + num[end] < sum)start++;elseend--;}sum += num[j];}}for(auto iter: result){results.push_back(iter);}return results;}
};

这篇关于LeetCode 题解（17）: 4Sum的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---