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