LeetCode第16题 最接近的三数之和

LeetCode第16题 最接近的三数之和

第一反应

和上一题很像，肯定用双指针循环，而且只要有一个输出就行，而且输出的只要是求出来的和就行。
预计还是先排序，然后双指针，然后内层循环依次遍历所有。但是好像不行，双指针的移动到底应该怎么移动，想不出来。要找最接近的一个三数之和，应该要遍历有可能的选项。
按照我上一个题解改一改的话，应该是两头的指针两层循环，第三个指针用二分查找，找到最接近target的值，然后保存下来，这样的复杂度是O(nnlogn)
先写写看

复习java

获取绝对值

Math.abs(数字)

提交通过

class Solution {
    int min_diff;
    boolean flag_pos;
    public int threeSumClosest(int[] nums, int target) {
        min_diff = 1000000; //用来保存与target的差值
        flag_pos = true;//指示是否是大于target
        Arrays.sort(nums);
        // for(int i = 0 ; i < nums.length ; i ++){
        //     System.out.print(nums[i] + " ");
        // }
        // System.out.println();
        int indexLow = 0;
        int indexHigh = nums.length-1;
        while(indexLow < nums.length-1 && indexHigh > indexLow +1){
            while(indexHigh > 1 && indexHigh > indexLow +1){
                // System.out.println("indexHigh = " + indexHigh + " ; indexLow = " + indexLow);
                int thirdNumber = target - nums[indexHigh] - nums[indexLow];
                searchB(nums, target, thirdNumber, indexLow+1, indexHigh-1);
                // System.out.println("thirdNumber = " + thirdNumber + " ; min_diff = " + min_diff + " ; flag_pos = " + flag_pos);

                indexHigh --;
                // indexHigh = nextIndex(nums, false, indexHigh);
            }
            indexLow ++;
            indexHigh = nums.length-1;
            // indexLow = nextIndex(nums, true, indexLow);
            // System.out.println("indexLow = " + indexLow);
            
        }
        if(flag_pos){
            return target + min_diff;
        }else{
            return target - min_diff;
        }
    }
    
    //二分查找
    private void searchB(int[] nums, int target,int thirdNumber, int beginIndex, int endIndex){
        if(beginIndex > endIndex){
            return ;
        }
        int mid = (beginIndex + endIndex) / 2;
        while(beginIndex < endIndex-1){
            if(Math.abs(nums[mid] - thirdNumber) < min_diff){
                min_diff = Math.abs(nums[mid] - thirdNumber);
                if(nums[mid] > thirdNumber){
                    flag_pos = true;
                }else{
                    flag_pos = false;
                }
            }
            if(nums[mid] == thirdNumber){
                return ;
            }else if(nums[mid] > thirdNumber){
                endIndex = mid;
            }else if(nums[mid] < thirdNumber){
                beginIndex = mid;
            }
            mid = (beginIndex + endIndex) / 2;
        }
        if(Math.abs(nums[mid] - thirdNumber) < min_diff){
            min_diff = Math.abs(nums[mid] - thirdNumber);
            if(nums[mid] > thirdNumber){
                flag_pos = true;
            }else{
                flag_pos = false;
            }
        }
        if(beginIndex < endIndex){
            mid ++;
            if(Math.abs(nums[mid] - thirdNumber) < min_diff){
                min_diff = Math.abs(nums[mid] - thirdNumber);
                if(nums[mid] > thirdNumber){
                    flag_pos = true;
                }else{
                    flag_pos = false;
                }
            }
        }
    }
}

题解

看了一个官方的题解，确实有道理，上一题应该也是类似的方法可以优化到O(n^2)。首先排序，然后确定一个数（比如最小的数a），然后另外两个数b和c用双指针，a+b+c如果大于target，就把c换成小的，反之亦然。这样就没啥问题，也很好理解，也比我写的好实现。