Same logic as 2sum but use all pairs, O(N^3), using hash map + set


  • 0
    J
    public class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            Set<Set<Integer>> resH = new HashSet<>();
            List<List<Integer>> res = new ArrayList<>();
            Map<Integer, List<int[]>> pairs = new HashMap<>();
            
            for(int i=0; i<nums.length; i++){
                for(int j=i+1; j<nums.length; j++){
                    int sum = nums[i] + nums[j];
                    List<int[]> x;
                    if(pairs.containsKey(target - sum)){
                        x = pairs.get(target - sum);
                    }else{
                        x = new ArrayList<>();
                    }
                    x.add(new int[]{i, j});
                    pairs.put(target - sum, x);
                }
            }
    
            for(int i=0; i<nums.length; i++){
                for(int j=i+1; j<nums.length; j++){
                    int sum = nums[i] + nums[j];
                    if(pairs.containsKey(sum)){
                        for(int[] firstTwo : pairs.get(sum)){
                            int[] quadIdx = new int[]{i, j, firstTwo[0], firstTwo[1]};
                            
                            boolean exit = false;
                            for(int k=0; k<4; k++){
                                for(int w=k+1; w<4; w++){
                                    if(quadIdx[k] == quadIdx[w]){
                                        exit = true;
                                        break;
                                    }
                                }
                                if(exit) break;
                            }
                            if(exit) continue;
                            
                            int[] quad = new int[]{quadIdx[0], quadIdx[1], quadIdx[2], quadIdx[3]};
                            
                            List<Integer> quadList = new ArrayList<>(4);
                            Set<Integer> quadSet = new HashSet<>();
                            for(int v : quad) { 
                                quadList.add(nums[v]);
                                quadSet.add(nums[v]);
                            }
                            
                            if(resH.contains(quadSet)) continue;
                            
                            resH.add(quadSet);
                            res.add(quadList);
                        }
                    }
                }
            }       
            return res;
        }
    }

  • 0
    J

    I am not positive to call this O(N^3) if anybody thinks this is wrong or has a tighter analysis please let me know thanks


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.