leetcode 18 -- 4Sum-白红宇

leetcode 18 -- 4Sum

阅读量：5278 次

发布时间：2019-06-14

本文共 2503 字，大约阅读时间需要 8 分钟。

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 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              using namespace std;vector
              
               
                > fourSum(vector
                
                 & nums, int target){ vector
                 
                  
                   >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
                   
                    
                     >sst; multimap
                     
                      >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
                      
                       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
                       
                        &s : sst){ vector
                        
                         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
                         
                           nums = { 1, 0, -1, 0, -2, 2}; //vector
                          
                            nums = {1, 0, -1, 0, -2, 2, -3, 3, -4, 4}; vector
                           
                            
                             >vvect; vvect = fourSum(nums, 0); for(const vector
                             
                              &ivec : vvect){ for(int i : ivec){ cout << i << " "; } cout << endl; } return EXIT_SUCCESS;}