1.4.1 雙指針技巧（一）

1.4.1 雙指針技巧（一）

來自專欄數據機構與演算法——雜記

在前一章中，我們通過迭代數組來解決一些問題。通常，我們只使用從第一個元素開始並在最後一個元素結束的一個指針來進行迭代。 但是，有時候，我們可能需要同時使用兩個指針來進行迭代。

示例

讓我們從一個經典問題開始：

反轉數組中的元素。

其思想是將第一個元素與末尾進行交換，再向前移動到下一個元素，並不斷地交換，直到它到達中間位置。

我們可以同時使用兩個指針來完成迭代：一個從第一個元素開始，另一個從最後一個元素開始。持續交換它們所指向的元素，直到這兩個指針相遇。

public static void reverse(int[] v, int N) { int i = 0; int j = N - 1; while (i < j) { swap(v, i, j); // this is a self-defined function i++; j--; }}

總結

總之，使用雙指針技巧的典型場景之一是你想要

從兩端向中間迭代數組。

這時你可以使用雙指針技巧：

一個指針從始端開始，而另一個指針從末端開始。

值得注意的是，這種技巧經常在排序數組中使用。

練習一：翻轉字元串

編寫一個函數，其作用是將輸入的字元串反轉過來。

示例 1:

輸入: "hello"輸出: "olleh"

示例 2:

輸入: "A man, a plan, a canal: Panama"輸出: "amanaP :lanac a ,nalp a ,nam A"

代碼：

class Solution { public String reverseString(String s) { char[] chars = s.toCharArray(); int i = 0, j = chars.length - 1; while(i < j){ char temp = chars[i]; chars[i] = chars[j]; chars[j] = temp; i++; j--; } return new String(chars); // 不能處理帶有回車的較長strng // String res = ""; // for(int i = 0; i < s.length(); i++){ // res = s.substring(i, i+1) + res; // } // return res; }}

練習二：拆分數組

給定長度為 2n 的數組, 你的任務是將這些數分成 n 對, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得從1 到 n 的 min(ai, bi) 總和最大。

示例 1:

輸入: [1,4,3,2]輸出: 4解釋: n 等於 2, 最大總和為 4 = min(1, 2) + min(3, 4).

提示:

1. n 是正整數,範圍在 [1, 10000].
2. 數組中的元素範圍在 [-10000, 10000].

代碼：

import java.util.*;class Solution { public int arrayPairSum(int[] nums) { Arrays.sort(nums); int sum = 0; for(int i = 0; i < nums.length; i+=2){ sum += nums[i]; } return sum; }}

練習三：兩數之和——輸入有序數組

兩數之和 II - 輸入有序數組

給定一個已按照升序排列 的有序數組，找到兩個數使得它們相加之和等於目標數。

函數應該返回這兩個下標值 index1 和 index2，其中 index1 必須小於 index2。

說明:

• 返回的下標值（index1 和 index2）不是從零開始的。
• 你可以假設每個輸入只對應唯一的答案，而且你不可以重複使用相同的元素。

示例:

輸入: numbers = [2, 7, 11, 15], target = 9 輸出: [1,2] 解釋: 2 與 7 之和等於目標數 9 。因此 index1 = 1, index2 = 2 。

代碼：

class Solution { public int[] twoSum(int[] numbers, int target) { int[] result = new int[2]; int sum = 0; for(int i = 0; i < numbers.length - 1; i++){ for(int j = i + 1; j < numbers.length; j++){ sum = numbers[i] + numbers[j]; if(sum == target){ result[0] = i + 1; result[1] = j + 1; return result; } } } return result; }}

推薦閱讀：