3Sum Closest

Question:

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Thinking:

Method1: Similar to 3Sum Runtime: 30 ms

	class Solution {
	    public int threeSumClosest(int[] nums, int target) {
	        int len = nums.length;
	        int d = Integer.MAX_VALUE;
	        Arrays.sort(nums);
	        for(int i = 0; i < len-2; i++){
	            if(i > 0 && nums[i-1] == nums[i]) continue;
	            int left = i+1; int right=len-1;
	            int tempTarget = target - nums[i];
	            while(left < right){
	                if(nums[left] + nums[right] == tempTarget) return target;
	                else if(nums[left] + nums[right] < tempTarget){
	                    if(Math.abs(target - nums[i] - nums[left] - nums[right]) < Math.abs(d))
	                        d = target-nums[i] - nums[left] - nums[right];
	                    left++;
	                } 
	                else{
	                    if(Math.abs(target - nums[i] - nums[left] - nums[right]) < Math.abs(d))
	                        d = target-nums[i] - nums[left] - nums[right];
	                    right--;
	                }
	            }
	        }
	        return target - d;
	    }
	}

Optimization Runtime: 22 ms

	class Solution {
	    public int threeSumClosest(int[] nums, int target) {
	        int len = nums.length;
	        int d = Integer.MAX_VALUE;
	        Arrays.sort(nums);
	        for(int i = 0; i < len-2; i++){
	            if(i > 0 && nums[i-1] == nums[i]) continue;
	            int left = i+1; int right=len-1;
	            while(left < right){
	                int t = target - nums[i] - nums[left] - nums[right];
	                if(t == 0) return target;
	                else if(t > 0){
	                    if(Math.abs(t) < Math.abs(d))
	                        d = t;
	                    left++;
	                } 
	                else{
	                    if(Math.abs(t) < Math.abs(d))
	                        d = t;
	                    right--;
	                }
	            }
	        }
	        return target - d;
	    }
	}

二刷

仍然和一刷的时候的方法类似，减少了不必要的判断，使用了三项表达式简化了代码逻辑。仍需要注意，在定义初始值时，需要根据target的正负值来赋值MAX_VALUE或MIN_VALUE。

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int low = 0, high = 0, res = target >= 0 ? Integer.MAX_VALUE: Integer.MIN_VALUE, sum = 0;
        Arrays.sort(nums);
        for(int i = 0; i < nums.length - 2; i ++){
            low = i + 1; high = nums.length - 1;
            while(low < high){
                sum = nums[i] + nums[low] + nums[high];
                if(sum == target) return target;
                else{
                    res = Math.abs(sum - target) < Math.abs(res - target) ? sum: res;
                    if(sum < target) low++;
                    else high--;
                }
            }
        }
        return res;
    }
}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier! Saves Data!