好傢伙，你管這破玩意叫 “雙指針”？

大家好，我是 程序員小熊 ，來自某大廠的程序員，今天給大家帶來一道亞馬遜的面試題，即 LintCode 1478 · 最接近 target 的值 ，提供 雙指針 的解題思路，供大家參考，希望對大家無論是刷題還是面試都有所幫助。

1478 · 最接近 target 的值

描述

給出一個數組，在數組中找到兩個數，使得它們的和最接近目標值但不超過目標值，返回它們的和。

解題思路

思考： 如果數組是已按照 升序排列 的，那麼這個題目是不是就很好做？那樣的話，可以定義兩個分別 指向數組的第一個元素和最後一個元素的指針，將兩個指針指向的元素和與目標值 target 進行比較，然後再根據比較的結果，決定移動那一個指針 。

但是由於題目沒有 告知數組是有序的 ，所以需要先對數組進行排序，然後再採用 雙指針 的策略去做。

注意點

當 數組長度小於 2 時，不存在滿足要求的結果，直接返回 -1；
由於題目要求找到的兩個數的和 最接近目標值但不超過目標值，因此只需要考慮找到的兩個數的和 小於等於目標值 即可，不需要考慮大於的情況。
定義變量 diff 用於保存當 target 大於等於 sum 時，target - sum 的值，並不斷更新（取最小值），diff 初始值設置爲 INT_MAX。

補充說明

注意點中的 第 3 點 中，diff 不斷更新取最小值的原因是 題目要求在數組找到兩個數的和最接近目標值但不超過目標值**，****diff = min(differ, target - sum)**。

舉慄

以 nums = [-18,-4,-6,13,4,4,16,-8]，target = 6 爲例子，如下分析：

1、原始數組

2、排序之後

3、採用雙指針

4、定義 diff

5、查找過程如下動圖

Show me the Code

c++

int closestTargetValue(int target, vector<int> &array) {
    int size = array.size();
    if (size < 2) {
        return -1;
    }

    sort(array.begin(), array.end());
    int left = 0, right = size - 1, diff = INT_MAX;
    while (left < right) {
        int sum = array[left] + array[right];
        if (sum > target) {
            right--;
        } else {
            diff = min(diff, target - sum);
            left++;
        }
    }
    return diff == INT_MAX ? -1 : target - diff;
}

java

int closestTargetValue(int target, int[] array) {
    int size = array.length;
    if (size < 2) {
        return -1;
    }

    Arrays.sort(array);
    int left = 0, right = size - 1, diff = Integer.MAX_VALUE;
    while (left < right) {
        int sum = array[left] + array[right];
        if (sum > target) {
            right--;
        } else {
            diff = Math.min(diff, target - sum);
            left++;
        }
    }
    return diff == Integer.MAX_VALUE ? -1 : target - diff;
}

1478 · 最接近 target 的值

解題思路

注意點

補充說明

舉慄

Show me the Code

c++

java

更多精彩

猜你喜歡