Share my 24-line Java code (beats 94.57% run times)


  • 9
    M
    public class Solution {
        public int threeSumClosest(int[] nums, int target) {
            Arrays.sort(nums);
            int diff = Integer.MAX_VALUE, closest = 0;
            for (int k=0; k<nums.length-2; ++k) {
                for (int i=k+1, j=nums.length-1; i<j; ) {
                    int sum = nums[k] + nums[i] + nums[j];
                    if (sum == target) { return target; }
                    else if (sum > target) {
                        if (sum-target < diff) {
                            diff = sum-target;
                            closest = sum;
                        }
                        --j;
                    } else {
                        if (target-sum < diff) {
                            diff = target-sum;
                            closest = sum;
                        }
                        ++i;
                    }
                }
            }
            return closest;
        }
    }

  • 0
    N

    I see your code is shorter and more concise. but I am just curious why it's faster? its still O(n^2). no offense.


  • 0
    M

    to be honest, i don't know, there is nothing unusual in my code. maybe i am just lucky (getting faster run time THIS TIME). i think it is quite ok if your run time is at the majority part of the run time distribution, which means you have no obvious algorithmic / implementation problem. then, the next thing to do is making the code clean, clear and concise.


  • 0
    W

    This is a great answer! One thing I am thinking about is whether we need to consider about stack overflow or not (for this line: int sum = nums[k] + nums[i] + nums[j];). I've seen several solutions but no one seems to consider about this.


  • 0
    M

    you mean nums[k] + nums[i] + nums[j] > Integer.MAX_VALUE? generally you do not need to consider this kind of edge cases. and btw, this is not stack overflow. stack overflow means number of frames in the caller stack exceeds its maximum limit, usually happens in recursive calls.


  • 0
    W

    Yes, you are right. Not stack overflow but integer overflow. :)


  • 0
    J
    public class Solution {
    public int threeSumClosest(int[] nums, int target) {
    	Arrays.sort(nums);
    	int diff = Integer.MAX_VALUE, closest = 0;
    	for (int k = 0; k < nums.length-2; k++) {
    		if (k > 0 && (nums[k] == nums[k-1]))//maybe batter
    			continue;
    		for (int i = k+1, j = nums.length-1; i < j; ) {
    			int sum = nums[k] + nums[i] + nums[j];
    			if (sum == target) {
    				return target;
    			} else if (sum > target) {
    				if (sum - target < diff) {
    					diff = sum - target;
    					closest = sum;
    				}
    				j--;
                    while((i < j) && (nums[j] == nums[j+1]))//maybe batter
    					j--;
    			} else {
    				if (target - sum < diff) {
    					diff = target - sum;
    					closest = sum;
    				}
                    i++;
    				while((i < j) && (nums[i] == nums[i-1]))//maybe batter
    					i++;
    			}
    		}
    	}
    	return closest;
      }
    }

Log in to reply
 

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