Clean and Short Accepted Java Based on 3sum


  • 0
    S

    According to 3sum, I used the same idea to create 4sum. I think my solution is easy to understand. It beats 60.41% users.

    public List<List<Integer>> fourSum(int[] nums, int target) {
            List<List<Integer>> res = new LinkedList<>();
            Arrays.sort(nums);
            for(int i = 0; i < nums.length - 3; i++){
                for(int j = nums.length - 1; j > 2; j --){
                    if((i == 0 || (i > 0 && nums[i-1] != nums[i])) && (j == nums.length - 1 || (nums[j] != nums[j + 1]))){
                        int low = i + 1, high = j - 1, temp = target - nums[i] - nums[j];
                        while(low < high){
                            if(nums[low] + nums[high] == temp){
                                res.add(Arrays.asList(nums[i], nums[low], nums[high], nums[j]));
                                while(nums[low] == nums[low + 1] && low < high)     low++;
                                while(nums[high] == nums[high - 1] && low < high)     high--;
                                low++;
                                high--;
                            }else if(nums[low] + nums[high] < temp)  low++;
                            else high--;
                        }
                    }
                }
            }
            return res;
        }
    

Log in to reply
 

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