­

好傢夥，你管這破玩意叫「雙指針」？

  • 2021 年 4 月 18 日
  • 筆記

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

1478 · 最接近target的值

描述

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

解題思路

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

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

注意點

  1. 當 數組長度小於 2 時，不存在滿足要求的結果，直接返回 -1；

  2. 由於題目要求找到的兩個數的和 最接近目標值但不超過目標值，因此只需要考慮找到的兩個數的和 小於等於目標值 即可，不需要考慮大於的情況。

  3. 定義變數 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++

 1 int closestTargetValue(int target, vector<int> &array) {
 2     int size = array.size();
 3     if (size < 2) {
 4         return -1;
 5     }
 6 
 7     sort(array.begin(), array.end());
 8     int left = 0, right = size - 1, diff = INT_MAX;
 9     while (left < right) {
10         int sum = array[left] + array[right];
11         if (sum > target) {
12             right--;
13         } else {
14             diff = min(diff, target - sum);
15             left++;
16         }
17     }
18     return diff == INT_MAX ? -1 : target - diff;
19 }

View Code

java

 1 int closestTargetValue(int target, int[] array) {
 2     int size = array.length;
 3     if (size < 2) {
 4         return -1;
 5     }
 6 
 7     Arrays.sort(array);
 8     int left = 0, right = size - 1, diff = Integer.MAX_VALUE;
 9     while (left < right) {
10         int sum = array[left] + array[right];
11         if (sum > target) {
12             right--;
13         } else {
14             diff = Math.min(diff, target - sum);
15             left++;
16         }
17     }
18     return diff == Integer.MAX_VALUE ? -1 : target - diff;
19 }

View Code

VirMach 便宜 VPS

QNews

QNews