Average N ^ 2 solution, easy understood


  • 0
    B

    Sort to make it easy to avoid duplicate solutions.
    First pass find the smaller two numbers, second pass to find the other two.
    Trick here is

    1. the second pass should find number whose index is bigger than its counterpart, otherwise, these four numbers should already be included in previous loop.
      2)second pass from end to beginning, this can handle the case that single number appear more than 2 times.
    public List<List<Integer>> fourSum(int[] nums, int target) {
            Arrays.sort(nums);
            HashMap<Integer,List<int[]>> sumMap = new HashMap<>();
    
            for(int i = 0;i<nums.length - 3;i++){
                if(i > 0 && nums[i] == nums[i - 1]) continue;
                for(int j = i+1;j<nums.length - 2;j++){
                    if(j > i + 1 && nums[j] == nums[j - 1]) continue;
                    int sum = nums[i] + nums[j];
                    List<int[]> sums = sumMap.get(sum);
                    if(sums == null){
                        sums = new ArrayList<>();
                        sumMap.put(sum,sums);
                    }
                    sums.add(new int[]{i,j});
                }
            }
    
            List<List<Integer>> ret = new ArrayList<>();
            for(int i = nums.length - 1;i>2;i--){
                if(i < nums.length - 1 && nums[i] == nums[i+1]) continue;
                for(int j = i-1;j>1;j--){
                    if(j < i - 1 && nums[j] == nums[j + 1]) continue;
                    int sum = nums[i] + nums[j];
                    List<int[]> smallers = sumMap.getOrDefault(target - sum , Collections.emptyList());
                    for(int[] smaller : smallers){
                        if(smaller[1] < j) ret.add(Arrays.asList(new Integer[]{nums[smaller[0]],nums[smaller[1]],nums[i],nums[j]}));
                    }
                }
            }
            return ret;
        }
    

Log in to reply
 

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