SHARE
TWEET

Untitled

a guest Apr 25th, 2019 52 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.    
  3.     Map<Integer, Map<String, List<Integer>>> pairs = new HashMap<>();
  4.    
  5.     Map<String, List<Integer>> results = new HashMap<>();
  6.  
  7.     Map<Integer, Integer> numbers = new HashMap<>();
  8.    
  9.     public List<List<Integer>> fourSum(int[] nums, int target) {
  10.        
  11.         for(int n : nums){
  12.             if( numbers.get(n) == null){
  13.                 numbers.put(n, 1);
  14.             }
  15.             else{
  16.                 numbers.put(n, numbers.get(n)+1);
  17.             }
  18.         }
  19.                
  20.         for(int x : numbers.keySet()){
  21.             for(int y : numbers.keySet()){
  22.                 if(x==y){
  23.                     if( numbers.get(x) == 1){
  24.                         continue;
  25.                     }
  26.                 }
  27.                
  28.                  List<Integer> r = new ArrayList<>();
  29.                    
  30.                  r.add(x);
  31.                  r.add(y);
  32.                  Collections.sort(r);
  33.                
  34.                  int sum = x + y;
  35.                
  36.                 if(pairs.get(sum) == null){
  37.                     Map<String, List<Integer>> p = new HashMap<>();
  38.                     p.put(toKey(r),r);
  39.                     pairs.put(sum, p);
  40.                 }
  41.                 else{
  42.                     Map<String, List<Integer>> p= pairs.get(sum);
  43.                     p.put(toKey(r),r );
  44.                     pairs.put(sum, p);
  45.                 }
  46.                
  47.             }
  48.         }
  49.        
  50.         for(int x : numbers.keySet()){
  51.             for(int y : numbers.keySet()){
  52.                 if(x==y){
  53.                     if( numbers.get(x) == 1){
  54.                         continue;
  55.                     }
  56.                 }
  57.                
  58.                 int needed = target - x - y;
  59.                
  60.                 if( pairs.get(needed) != null){
  61.                     Map<String, List<Integer>> p = pairs.get(needed);
  62.                    
  63.                     for( String k: p.keySet()){
  64.                         List<Integer> pair = p.get(k);
  65.                         int a = pair.get(0);
  66.                         int b = pair.get(1);
  67.                        
  68.                         Map<Integer, Integer> counts = new HashMap<>();
  69.                      
  70.                         countNum(x,counts);
  71.                         countNum(y,counts);
  72.                         countNum(a,counts);
  73.                         countNum(b,counts);
  74.                        
  75.                         boolean skip = false;
  76.                        
  77.                         for(int n : counts.keySet()){
  78.                            
  79.                            
  80.                             if(numbers.get(n) < counts.get(n)){
  81.                                 skip =true;
  82.                                 break;
  83.                             }
  84.                         }
  85.                        
  86.                         if(skip){
  87.                             continue;
  88.                         }
  89.                        
  90.                         List<Integer> r = new ArrayList<>();
  91.                    
  92.                          r.add(x);
  93.                          r.add(y);
  94.                         r.add(a);
  95.                          r.add(b);
  96.                          Collections.sort(r);
  97.                
  98.                         results.put(toKey(r), r);
  99.                        
  100.                     }
  101.                 }
  102.             }
  103.         }
  104.        
  105.         List<List<Integer>> ret = new ArrayList<>();
  106.        
  107.         for(String s : results.keySet()){
  108.             ret.add(results.get(s));
  109.         }
  110.        
  111.         return ret;
  112.     }
  113.    
  114.    
  115.     public void countNum(int num, Map<Integer, Integer> map){
  116.         if(map.get(num) ==null){
  117.             map.put(num,1);
  118.         }
  119.         else{
  120.             map.put(num, map.get(num)+1);
  121.         }
  122.     }
  123.        
  124.     public String toKey(List<Integer> nums){
  125.        
  126.         String ret = "";
  127.        
  128.         for(int x : nums){
  129.             ret += "+"+x;
  130.         }
  131.         return ret;
  132.     }
  133.    
  134. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top