Leetcode-18-4Sum

Posted 2022-07-14

9~12 min read

4Sum

leetcode: https://leetcode.com/problems/4sum/

Description:

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Idea:

**solution:two poiners **

Step1: sort the array(to the verify the sum), and create the array list

Step2: use first index and second index to traverse the nums, because this nums array has been sorted, if current element it pointed bigger than 0, it means another two element will >0, the sum of theme can’t meet the requirement, return the current result. At the same time, if this element is equal to it’s next element, we skip next element to avoid the repeated combiantion in the result.

Step3: to set two pointers to get the bound of another two elements. Because the array is sorted, so if the sum >0, we need to move the right index to it’s previous poisiton to make the sum smaller. if sum< 0 , then move the left pointer to the next.

Step4: if the sum =0, record this combination, and use while loop to skip the continous same element of the left and right side to avoid repeated combinations in the result. Then, narrowing the bound to search next combination.

Code:

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        //sort the array, so more easier to adjust the index range by verifing the sum
        Arrays.sort(nums);
        //create list to store result array
        List<List<Integer>> result = new ArrayList<>();
        //use the first index to traverse array
        for(int i=0; i<nums.length; i++){
            //avoid repeated result
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for(int j= i+1; j<nums.length; j++){
                if (j>i+1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                //set two pointer to get all possible combination
                int l_index=j+1;
                int r_index = nums.length-1;
                while(l_index < r_index){
                    // because the number is 10^9, use long data type, make varibale * 1L to use the variable as long type
                    long sum = nums[i]*1l + nums[j] + nums[l_index] + nums[r_index];
                    //sum>target
                    if(sum>target){
                        r_index--;
                    }
                    //sum<target
                    else if(sum<target){
                        l_index++;
                    }
                    //sum ==target
                    else{
                        //add current combination array to list
                        result.add(Arrays.asList(nums[i], nums[j],nums[l_index], nums[r_index]));
                        //avoid repeated result(if current index meet the rquirement, and next element is same, skip it)
                        while(l_index<r_index && nums[l_index] == nums[l_index+1]){
                            l_index++;
                        }
                        while(l_index<r_index && nums[r_index] == nums[r_index-1]){
                            r_index--;
                        }
                        //remove left and right index to adjust the range
                        l_index++;
                        r_index--;
                    }
                }
            }
        }
        return result;
    }
}

sum of more elements: can also use this method, and add loop to it

Leetcode

Leetcode Hash