Friday, September 13, 2013

3Sum Closest

Q: 
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
    For example, given array S = {-1 2 1 -4}, and target = 1.

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

A:

 


----------------------第三遍----就是2sum外边套了个循环-----------------而且如果小,就增加j,如果大,就减少k,每次都比较,看是否更新closest就行了。

public class Solution {
        if(nums.length<3)
            throw new IllegalArgumentException("at least 3 values");
        int closest = nums[0]+ nums[1]+ nums[2];
        Arrays.sort(nums);
        for(int i =0;i<nums.length;i++){
            int j = i+1, k = nums.length-1;
            while(j<k){
                if ( Math.abs(target - nums[i] - nums[j]  - nums[k] )< Math.abs(target-closest))
                    closest = nums[i] + nums[j]  + nums[k];
                if(nums[i] + nums[j]  + nums[k] <= target)
                    j++;
                else 
                    k--;
            }
        }
        return closest;        
    }
}


Error:




----------------1st pass --------------------------
思路同3Sum,但是,这个时候,是测量距离最近的triplet, 并记录下来。

public class ThreeSumClosest {
    public int threeSumClosest(int[] num, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        Arrays.sort(num);
        if (num.length < 3) { // something is wrong
            return Integer.MAX_VALUE;
        }

        int smallerClosest = threeSumSmallerClosest(num, target);
        int biggerClosest =  threeSumBiggerClosest(num, target);

        if (Math.abs(smallerClosest - target) < Math
                .abs(biggerClosest - target)) {
            return smallerClosest;
        } else {
            return biggerClosest;
        }

    }

    private int threeSumBiggerClosest(int[] num, int target) {
        // find the max three sum that is slightly bigger than
        // target.(difference is minimum)

        int biggerClosest = num[num.length - 1] + num[num.length - 2]
                + num[num.length - 3];
        // num is already sorted
        for (int i = 0; i < num.length - 2; i++) {
            // now treat the inner two
            int j = i + 1;
            int k = num.length - 1;
            while (j < k) { // loop of the j index
                // loop update of the k index
                while (k > j + 1 && num[i] + num[j] + num[k] > target) {
                    if (biggerClosest > (num[i] + num[j] + num[k])
                            && (num[i] + num[j] + num[k]) >= target) {
                        biggerClosest = num[i] + num[j] + num[k];
                    }
                    k--;
                }
                
                j++;
            }
        }
        return biggerClosest;
    }

    private int threeSumSmallerClosest(int[] num, int target) {

        int smallerClosest = num[0] + num[1] + num[2];
        // num is already sorted
        for (int i = 0; i < num.length - 2; i++) {
            // now treat the inner two
            int j = i + 1;
            int k = num.length - 1;
            while (j < k) { // loop of the j index
                // When i Is fixed, if j is also fixed, we
                // find the three Sum that is less than target, by decreasing k
                while (k > j + 1 && num[i] + num[j] + num[k] > target) {
                    k--;
                }
                // after above loop, -------> num[i] + num[j] + num[k] < target
                // ( but there might be no loop at all
                // Now three Sum is smaller than target
                if (smallerClosest < (num[i] + num[j] + num[k])
                        && (num[i] + num[j] + num[k]) <= target) {
                    smallerClosest = num[i] + num[j] + num[k];
                }
                j++;
            }
        }
        return smallerClosest;
    }

}

Mistakes:
1: TMMD, 还是没有透彻得明白two pointer 为什么那样。 以致于  思路有点儿混乱。
      最终,还是分成了两种情况考虑的。

2: 当判断 threeSum 和现在的是否想等,  就是在k的while语句中,可以没有==, 但是,再实际判断的时候,是需要的, 因为,当想到的时候,也是可以的
if (biggerClosest > (num[i] + num[j] + num[k])
                            && (num[i] + num[j] + num[k]) >= target) {
--------------第二遍的时候,   就是用了对p0固定后, 找最近的两个value,   
3 :  不能简单的把 target  - num[p0]传进去, 要两个都传, 因为里面有个  Math.abs()的操作, 谁知道,target 对num[p0] 是加还是减呢
4: closeSum 设初值的时候,不能乱设,谁知道这个值在3sum里能不能出现呀。
       更不能  设为Integer.Max_VALUE什么的,  会出现边界值。


No comments:

Post a Comment