leetcode 18 -- 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)

---

题意：
找寻一个数组中满足条件的一组元素，条件为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的数可以了。下标我们都记录着，所以很容易得到原先的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;
}

测试结果：
第一组

第二组