leetcode16. 最接近的三數之和--每天刷一道leetcode算法系列!

作者：reed，一個熱愛技術的斜槓青年，程式設計師面試聯合創始人

題目描述

給定一個包括 n 個整數的數組 nums 和 一個目標值 target。找出 nums 中的三個整數，使得它們的和與 target 最接近。返回這三個數的和。假定每組輸入只存在唯一答案。

例如，給定數組 nums = [-1，2，1，-4], 和 target = 1.
與 target 最接近的三個數的和為 2. (-1 + 2 + 1 = 2).

分析

本題最容易想到的方法應該就是暴力破解，但是靠暴力破解的話時間複雜度會到 O(n^3)，面試中顯然不能讓面試官滿意。
採取如下方式可以將時間複雜度優化為 O(n^2)。
首先對數組進行排序，排序的時間複雜度 O(nlogn)。
在數組 nums 中，進行遍歷，每遍歷一個值取其下標i，形成一個固定值 nums[i]
再使用左指針 left = i + 1 ，右指針 right = nums.length - 1 。
根據 sum = nums[i] + nums[left] + nums[right] 的結果，
並判斷 sum 與 target 的大小關係，因為數組有序，如果 sum == target 則說明距離為 0 直接返回結果，如果 sum < target 則 left++，如果 sum > target 則 right--，並不斷更新返回值。
整個遍歷過程時間複雜度為 O(n^2)
因此總時間複雜度：O(n^2)。

代碼

public int threeSumClosest(int[] nums, int target) {
        assert nums.length > 2;
        Arrays.sort(nums);
        int left;
        int right;
        int sum3;  //數組中的三個數的和
        int res = 0;  //記錄返回結果
        int tmp = Integer.MAX_VALUE; //記錄sum3和target的差的絕對值
        for (int i = 0; i < nums.length - 2; i++) {
            left = i + 1;
            right = nums.length - 1;
            while (left < right) {
                sum3 = nums[left] + nums[right] + nums[i];
                //如果已經找到等於target的三個數，直接返回即可。
                if (sum3 == target) {
                    return target;
                }
                if (Math.abs(sum3 - target) < tmp) {
                    tmp = Math.abs(sum3 - target);
                    res = sum3;
                }
                if (sum3 > target) {
                    right--;
                } else {
                    left++;
                }
            }

        }

        return res;
    }

長按訂閱更多面經分享