问题描述：

  从一些数中取出四个，使和等于N，可任意重复取，求所有的情况。 与以下题目相似

解题思路：

•   暴力解法（四重循环），效率很低

•   利用hash的方法：先将数据两两相加，将和作为key,将两个数据组成的集合作为值value；由于相同的和值的组合可能有多个，所以 value应该是一个多种组合的集合。以下是我的一种实现，个人感觉代码不够简洁，但一时没有找到优化思路，先贴到这里，希望将来能够找到更好的方法，也希望有人看到问题的话能够指正出来

•  其他解决方法，比如：动态规划

  hash方法的代码如下：

   

  public class Solution {    public ArrayList
         
          
           > fourSum(int[] num, int target) {         ArrayList
           
            
             > arrlist = new ArrayList
             
              
               >(); //为了去重 Set
               
                
                 > finalsetlist = new HashSet
                 
                  
                   >(); int len =num.length; if(len<4){ return null; } //先排序 int[] numtemp = sort(num); System.out.print("排序之后："); for(int nu:numtemp){ System.out.print(nu+" "); } System.out.println(); //判断最大的四个数是否大于target int maxlastfour =0; //判断最小的四个数是否小于target int minfirstfour =0; for(int i=len-1;i>len-5;i--){ maxlastfour +=numtemp[i]; } System.out.println("最大的四个数之和："+maxlastfour); if(maxlastfour
                   
                    target){ return null; } //利用hash原理，先计算两个数的和 Map
                    
                     
                      
                       >> map = new HashMap
                       
                        
                         
                          >>(); //将每两个数相加，和为key，这两个数的组合为value,考虑到和等于target的组合有多种，用set集合保存各种组合可能 for(int i=0;i
                          
                           > set =null; int key = numtemp[i]+numtemp[j]; if(!map.containsKey(key)){ set = new HashSet
                           
                            
                             >(); List
                             
                               list = new ArrayList
                              
                               (); list.add(numtemp[i]); list.add(numtemp[j]); set.add(list); map.put(key,set); }else{ set = map.get(key); List
                               
                                 list = new ArrayList
                                
                                 (); list.add(numtemp[i]); list.add(numtemp[j]); set.add(list); map.put(key,set); } } } //排序以后 Map
                                 
                                  
                                   
                                    >> mapresult = new HashMap
                                    
                                     
                                      
                                       >>(); List
                                       
                                        
                                         >>> maplist = new ArrayList
                                         
                                          
                                           >>>(map.entrySet()); Collections.sort(maplist,new Comparator
                                           
                                            
                                             
                                              
                                               >>>(){ public int compare(Map.Entry
                                               
                                                
                                                 
                                                  >> map1,Map.Entry
                                                  
                                                   
                                                    
                                                     >> map2){ return map1.getKey().compareTo(map2.getKey()); } }); for(Map.Entry
                                                     
                                                      
                                                       
                                                        >> mapen:maplist){ mapresult.put(mapen.getKey(), mapen.getValue()); } //从hash表中查找是否存在这样的组合 Set
                                                        
                                                          keys = mapresult.keySet(); for(Integer k:keys){ int firtwo = k; Set
                                                         
                                                          
                                                           > setvaluefir = mapresult.get(firtwo); int sectwo = target-firtwo; Set
                                                           
                                                            
                                                             > setvaluelas = mapresult.get(sectwo); if((mapresult.get(Integer.valueOf(sectwo))!=null)&&(mapresult.get(Integer.valueOf(sectwo)).size()>0)){ for(List
                                                             
                                                               listvalue:setvaluefir){ for(List
                                                              
                                                                listvalue1:setvaluelas){ ArrayList
                                                               
                                                                 arr = new ArrayList
                                                                
                                                                 (); arr.addAll(listvalue); arr.addAll(listvalue1); //按升序输出 Collections.sort(arr); finalsetlist.add(arr); //arrlist.add(arr); } } } } for(ArrayList
                                                                 
                                                                   arrli:finalsetlist){ arrlist.add(arrli); } return arrlist; } //排序 public int[] sort(int[] num){ int[] numtemp = num; int numlen = numtemp.length; for(int i=0;i
                                                                  
                                                                   numtemp[j]){ int temp = numtemp[i]; numtemp[i] = numtemp[j]; numtemp[j] =temp; } } } return numtemp; }}