Simple explanation O(n^2)


  • 0
    N

    Well the idea here is simple,we do a reduction for this problem
    we iterate through the array picking each number at a time,and reducing it from the target
    now the question is reducted to a simpler question,finding closest 2 sum.
    and that can be done with 2 pointers.

    here's a code for it

    public static int threeSumClosest(int[] nums, int target) {
    		int minS = nums[0]+nums[1]+nums[2];
    		Arrays.sort(nums);
    		for (int k = 0; k < nums.length - 2; k++) {
    			int temp = twoSum(nums, target - nums[k], k + 1) + nums[k];
    			minS = Math.abs(temp - target) < Math.abs(minS - target) ? temp : minS;
    		}
    		return minS;
    	}
    
    	public static int twoSum(int[] numbers, int target, int start) {
    
    		int end = numbers.length - 1;
    		int minS = numbers[start]+numbers[start+1];
    		int minDiff = target;
    		while (start < end) {
    			if (Math.abs((numbers[end] + numbers[start]) - target) < Math.abs(minDiff)) {
    				minDiff = Math.abs((numbers[end] + numbers[start]) - target);
    				minS = numbers[end] + numbers[start];
    			}
    			if (numbers[end] + numbers[start] > target)
    				end = end - 1;
    			else if (numbers[end] + numbers[start] < target)
    				start = start + 1;
    			else
    				return numbers[end] + numbers[start];
    		}
    		return minS;
    	}
    

Log in to reply
 

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