Easy to understand extensible Java solution beat 95% with explanation


  • 0
    F
    public List<List<Integer>> fourSum2(int[] nums, int target) {
    	if (nums == null || nums.length < 4)
    		return res;
    	ArrayList<List<Integer>> res = new ArrayList<>();
    	Arrays.sort(nums);
    
    	if (nums[0] * 4 > target || nums[nums.length - 1] * 4 < target) { 
    		return res;
    	}
    	
    	//following is four sum:
    	for (int i = 0; i < nums.length - 3; i++) {
    		if (nums[i] + nums[nums.length - 1] * 3 < target) //nums[i] is too small
    			continue;
    		if (nums[i] * 4 > target) { //nums[i] is too big
    			break;
    		}
    
    		if (i > 0 && nums[i] == nums[i - 1]) //jump duplicate
    			continue;
    		
    		//following is three sum:
    		for (int j = i + 1; j < nums.length - 2; j++) {
    			if (nums[i] + nums[j] + nums[nums.length - 1] * 2 < target) //nums[j] is too small
    				continue;
    			if (nums[i] + nums[j] * 3 > target) { //nums[j] is too big
    				break;
    			}
    
    			if (j > i + 1 && nums[j] == nums[j - 1]) //jump duplicate
    				continue;
    			
    			//following is two sum:
    			int low = j + 1, high = nums.length - 1;
    			while (low < high) {
    				int sum = nums[i] + nums[j] + nums[low] + nums[high];
    				if (sum == target) {
    					res.add(Arrays.asList(nums[i], nums[j], nums[low],
    							nums[high]));
    					while (low < high && nums[low] == nums[low + 1]) //jump duplicate
    						low++;
    					while (low < high && nums[high] == nums[high - 1]) //jump duplicate
    						high--;
    					low++;
    					high--;
    				} else if (sum < target)
    					low++;
    				else
    					high--;
    			}
    		}
    	}
    	return res;
    }

  • 0

    I'm a new user,please tell me how to give my code like yours when i make comments.


  • 0
    F

    I just made comments in eclipse, and copy&paste here. Hope that could hep you!


Log in to reply
 

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