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)

---

題意：
找尋一個數組中滿足條件的一組元素，條件為4個數的和值為0。

上面有樣例，要求1.返回一組元素中不能反復。2.每一個元素的4個值必須是有序的比方(-1, 0, 0, 1)。a <= b <= c <=d。

---

思路：
先對給定數組做初始化，把全部兩兩值的和求出來，我們就把求4Sum變為求2Sum了。注意初始化的時候求兩兩和值也要保存兩個數字的下標，題中我用的是multimap <int, pair < int, int > >，由于可能會有反復的所以要用multimap, multimap第一個int是表示和值。第二個pair是兩個數的下標，并且用multimap我們默認是排序的，剛好初始化完直接用首和尾指針查找滿足2Sum為0的數能夠了。下標我們都記錄著。所以非常easy得到原先的4個值。

找到4個值后我們把它保存在set中，這樣也滿足題意的要求返回值是有序的。

---

代碼：

#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <iostream> #include <map> #include <vector> #include <set> #include <algorithm>using namespace std;vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>>ret;//兩個特殊情況if(nums.size() < 4){return ret;}if(nums.size() == 4){if(accumulate(nums.begin(), nums.end(), 0) == 0){ret.push_back(nums);}return ret;}//里面的set是為了滿足排序條件，外面的set是為了滿足不反復條件set<set<int>>sst;multimap<int, pair<int, int>>two_sum;//求兩兩和值for(int i = 0; i < nums.size(); ++i){for(int j = i+1; j != nums.size(); ++j){two_sum.insert({nums[i]+nums[j], {i,j}});}}//定義首尾指針auto iter1 = two_sum.begin();//注意iter2不能為two_sum.end()-1,由于two_sum是基于map的沒有迭代器減法和加法auto iter2 = --two_sum.end();while(iter1 != iter2){set<int>st;int add = iter1->first + iter2->first;//滿足條件。加入到set中if(add == 0){st.insert(iter1->second.first);st.insert(iter1->second.second);st.insert(iter2->second.first);st.insert(iter2->second.second);//假設為4個數字說明無反復且和為0，加入到外層set中if(st.size() == 4){sst.insert(st);}++iter1;--iter2;}else if(add < 0){++iter1;}else if(add > 0){--iter2;}}//將set中的元素加入到vector中返回就可以for(const set<int>&s : sst){vector<int>tmp;for(auto i = s.begin(); i != s.end(); ++i){tmp.push_back(nums[*i]);}sort(tmp.begin(), tmp.end());ret.push_back(tmp);}return ret; }int main(int argc, char *argv[]) {vector<int> nums = {1, 0, -1, 0, -2, 2};//vector<int> nums = {1, 0, -1, 0, -2, 2, -3, 3, -4, 4};vector<vector<int>>vvect;vvect = fourSum(nums, 0);for(const vector<int>&ivec : vvect){for(int i : ivec){cout << i << " ";}cout << endl;}return EXIT_SUCCESS; }

測試結果：
第一組

第二組

轉載于:https://www.cnblogs.com/blfshiye/p/5397614.html

總結

以上是生活随笔為你收集整理的leetcode 18 -- 4Sum的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。