python-雙指針

目錄

​​核心思想​​

​​一、快慢指針​​

​​思路：​​

​​解答：​​

​​二、對撞指針​​

​​三、滑動視窗​​

核心思想

1.兩個指針，其中一個指針周遊所有元素，另一個元素根據條件判斷是否移動

2.達到一定條件，将兩個指針指向的元素，互換，list[i],list[j]=list[j],list[i]

一、快慢指針

力扣27        力扣（LeetCode）

給你一個數組 nums 和一個值 val，你需要 原地 移除所有數值等于 val 的元素，并傳回移除後數組的新長度。

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

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

思路：

解答：

class Solution:
    def removeElement(self, nums, val):
        j = 0  # 慢指針,j
        for i in range(len(nums)):  # 快指針,i開始周遊
            if nums[i] != val:  # 快指針隻要發現不為val的值，就把它往前放（這是最核心的思想）
                nums[i], nums[j] = nums[j], nums[i]     # 這裡不需要考慮慢指針的情況，因為慢指針肯定為val值
                # 因為快指針比慢指針快，他把後面的非val都移動走了，慢指針遇不到非val元素
                j += 1
        return j, nums      

二、對撞指針

class Solution:
    def removeElement(self, nums, val):
        i = 0  # 左指針
        j = len(nums) - 1  # 右指針
        while j >=i:
            if nums[j] != val:
                if nums[i] == val:
                    nums[j], nums[i] = nums[i], nums[j]
                    i = i + 1
                    j = j - 1
                else:
                    i = i + 1
            else:
                j = j - 1

        return i      

三、滑動視窗