七十三、從三數(shù)之和探究雙指針思想

「@Author：Runsen」

編程的本質(zhì)來源于算法，而算法的本質(zhì)來源于數(shù)學(xué)，編程只不過將數(shù)學(xué)題進行代碼化。「---- Runsen」

雙指針

雙指針是一種解決問題的技巧或者思維方式，指在訪問一個序列中的數(shù)據(jù)時使用兩個指針進行掃描，兩個指針可以是同向的，也可以是反向的。

我們的關(guān)注點可以是這兩個指針指向的兩個元素本身，也可以是兩個指針中間的區(qū)域。二分法的思想基于這種左右指針的實現(xiàn)。

雙指針是一種思想，一種技巧或一種方法，并不是什么特別具體的算法。在區(qū)間問題上，暴力的做法的復(fù)雜度往往達到復(fù)雜度，而雙指針的思想挖掘區(qū)間“單調(diào)”性質(zhì)將復(fù)雜度降到。

常用的雙指針思想有：快慢指針、碰撞指針、滑動窗口等。

快慢指針：快慢指針按照某種規(guī)律運動。例如，設(shè)置快慢兩個指針，快指針先移動距離，慢指針跟快指針同時移動，這樣快慢指針之間總是保持一段相同的距離。常見的應(yīng)用場景主要出現(xiàn)在鏈表中，如：鏈表的環(huán)的判斷，求鏈表的中間節(jié)點等操作。

碰撞指針：在排序好的數(shù)組中，設(shè)置頭指針和尾指針，按照規(guī)則，分別向中間靠攏。常見的應(yīng)用場景主要出現(xiàn)在有序數(shù)組中：數(shù)組的和，二分查找等。「這里需要強調(diào)的是：對于碰撞指針要用于已排序的區(qū)間?！?/strong>

滑動窗口：兩個指針，一前一后組成滑動窗口，并計算滑動窗口中的元素的問題。常見問題：字符串匹配問題等，用來解決一些查找滿足一定條件的連續(xù)區(qū)間求值或長度的問題。

LeetCode 第 15題：三數(shù)之和

給你一個包含 n 個整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有滿足條件且不重復(fù)的三元組。

注意：答案中不可以包含重復(fù)的三元組。

示例： 
給定數(shù)組 nums = [-1, 0, 1, 2, -1, -4]，
滿足要求的三元組集合為：
[
 [-1, 0, 1],
 [-1, -1, 2]
]

在Leetcode上第一題是兩數(shù)之和，使用Hashmap儲存，時間復(fù)雜度是。

如果三數(shù)之和使用該方法，時間復(fù)雜度是。題目中說的不可以包含重復(fù)的三元組，然后在去去重，這樣是非常費時的，很容易超時但是過高的時間復(fù)雜度導(dǎo)致代碼編譯效率極差，我記得很清楚Leetcode不給予通過。這種方法是在面試中實在想不出其他解法時的選擇.....

雙指針思路：采取左右兩個指針代替兩個for循環(huán)，在第一層循環(huán)下調(diào)節(jié)指針的位置，設(shè)置判斷條件就可以排除很多重復(fù)項和不滿足條件的組合，最終得到滿足題目的三元組，具體的偽代碼大致如下：

function fn (list) {
  var left = 0;
  var right = list.length - 1;

  //遍歷數(shù)組
  while (left <= right) {
    left++;
    // 一些條件判斷 和處理
    ... ...
    right--;
  }
}

由于本提中給出的數(shù)組是未排序，且有重復(fù)數(shù)據(jù)的情況，所以首先需要做排序和去重處理

下面使用排序 + 雙指針方法解決：

看到這張概念圖后，是不是已經(jīng)有內(nèi)味了？

• 首先進行數(shù)組排序，時間復(fù)雜度 O(nlogn)
• 對數(shù)組nums進行遍歷，每遍歷一個值利用其下標 i，形成一個固定值 nums[i]
• 如果 nums[i]大于0， 則三數(shù)之和必然無法等于0，直接結(jié)束循環(huán)
• 如果 nums[i] == nums[i-1]，則說明該數(shù)字重復(fù)，會導(dǎo)致結(jié)果重復(fù)，所以應(yīng)該跳過
• 再使用前指針指向 l = i + 1處，后指針指向r = nums.length - 1，也就是結(jié)尾處
• 根據(jù) three_sum = nums[i] + nums[l] + nums[r]結(jié)果，判斷 three_sum 與 0 的大小關(guān)系，滿足則添加進入結(jié)果，此時 l+=1和 r-=1。如果 three_sum < 0，則l+=1, 如果 three_sum > 0, 則 `r-=1``
• three_sum === 0 的時候還要考慮結(jié)果重復(fù)的情況
• nums[l] == nums[l+1] 則會導(dǎo)致結(jié)果重復(fù)，應(yīng)該跳過，l++
• nums[r] == nums[r-1] 則會導(dǎo)致結(jié)果重復(fù)，應(yīng)該跳過，r--
• 總時間復(fù)雜度：

具體查看代碼：

class Solution:
    def threeSum(nums):
    nums.sort()
    # [-4, -1, -1, 0, 1, 2]
    res_list = []
    # 頭部循環(huán)查找
    for i in range(len(nums)):
        if i == 0 or nums[i] > nums[i - 1]:
            # 最左端
            l = i + 1
            # 最右端
            r = len(nums) - 1
            while l < r:  # 正在查找
                three_sum = nums[i] + nums[l] + nums[r]
                if three_sum == 0:
                    res_list.append([nums[i], nums[l], nums[r]])
                    l += 1  # 右移一位
                    r -= 1  # 左移一位
                    while l < r and nums[l] == nums[l - 1]:
                        # 從左往右，相同數(shù)值直接跳過
                        l += 1
                    while r > l and nums[r] == nums[r + 1]:
                        # 從右往左，相同數(shù)值直接跳過
                        r -= 1
                elif three_sum > 0:
                    # 大于零，右邊數(shù)值大，左移
                    r -= 1
                else:
                    # 小于零，左邊數(shù)值小，右移
                    l += 1
    return res_list

LeetCode 第 16題：最接近的三數(shù)之和

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

示例： 
輸入：nums = [-1,2,1,-4], target = 1
輸出：2
解釋：與 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
提示： 
3 <= nums.length <= 10^3 
-10^3 <= nums[i] <= 10^3 
-10^4 <= target <= 10^4 

本題目因為要計算三個數(shù)，如果靠暴力枚舉的話時間復(fù)雜度會到，需要降低時間復(fù)雜度，借鑒上面的三數(shù)之和，其實兩道題的解決思路幾乎一樣，只不過這道題需要不停著記錄三個數(shù)的和與 target 之間的差。

• 首先進行數(shù)組排序，時間復(fù)雜度O(nlogn)
• 在數(shù)組nums中，進行遍歷，每遍歷一個值利用其下標i，形成一個固定值nums[i]
• 再使用前指針指向j= i + 1處，后指針指向k= nums.length - 1處，也就是結(jié)尾處
• 根據(jù) sum = nums[i] + nums[start] + nums[end]的結(jié)果，判斷sum與目標target的距離，如果更近則更新結(jié)果ans
• 同時判斷sum與target的大小關(guān)系，因為數(shù)組有序，如果sum > target 則k--，如果sum < target 則 j++，如果sum == target 則說明距離為0直接返回結(jié)果
• 整個遍歷過程，固定值為n次，雙指針為n次，時間復(fù)雜度為O(n^2)
• 總時間復(fù)雜度：

具體查看代碼：

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        if not nums: return 0
        if len(nums) < 3: return sum(nums)

        ans = float('inf')
        nums.sort()
        for i in range(len(nums)):
            # 優(yōu)化點 1
            if i > 0 and nums[i] == nums[i-1]: 
                continue
            
            t = target - nums[i]
            j, k = i + 1, len(nums) - 1
            while j < k:
                # 優(yōu)化點 2
                if t == nums[j] + nums[k]: return target

                # 當(dāng)前 j、k更接近target
                if abs(t - nums[j] - nums[k]) < abs(target - ans):
                    ans = nums[i] + nums[j] + nums[k]
                # 移動j | k
                if t > nums[j] + nums[k]:
                    j += 1
                else:
                    k -= 1
        return ans

LeetCode 第 27題：移除元素

給你一個數(shù)組 nums 和一個值 val，你需要 原地 移除所有數(shù)值等于 val 的元素，并返回移除后數(shù)組的新長度。

不要使用額外的數(shù)組空間，你必須僅使用 O(1) 額外空間并 原地 修改輸入數(shù)組。

元素的順序可以改變。你不需要考慮數(shù)組中超出新長度后面的元素。

示例 1:
給定 nums = [3,2,2,3], val = 3,
函數(shù)應(yīng)該返回新的長度 2, 并且 nums 中的前兩個元素均為 2。
你不需要考慮數(shù)組中超出新長度后面的元素。
示例 2:
給定 nums = [0,1,2,2,3,0,4,2], val = 2,
函數(shù)應(yīng)該返回新的長度 5, 并且 nums 中的前五個元素為 0, 1, 3, 0, 4。
注意這五個元素可為任意順序。

首先講講自己做題的思路，用Python做比較簡單，遍歷數(shù)組，如果當(dāng)前值不等于val，就是i += 1

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i = 0
        for num in nums:
            if num != val:
                nums[i] = num
                i += 1
        return i

官方的解法是雙指針，我們可以保留兩個指針 i 和 j，其中 i 是慢指針，j 是快指針。

public int removeElement(int[] nums, int val) {
    int i = 0;
    for (int j = 0; j < nums.length; j++) {
        if (nums[j] != val) {
            nums[i] = nums[j];
            i++;
        }
    }
    return i;
}

人生最重要的不是所站的位置，而是內(nèi)心所朝的方向。只要我在每篇博文中寫得自己體會，修煉身心；在每天的不斷重復(fù)學(xué)習(xí)中，耐住寂寞，練就真功，不畏艱難，奮勇前行，不忘初心，砥礪前行，人生定會有所收獲，不留遺憾 （作者：Runsen ）

本文已收錄 GitHub，傳送門~^[1] ，里面更有大廠面試完整考點，歡迎 Star。