leetcode-Double_Pointer

双指针

双指针的思想和滑动窗口类似，不同的是双指针使用的是相向运动的滑窗，双指针技巧主要分为两类：左右指针和快慢指针。

left = 0

right = len(nums) – 1

双指针一般用于使用已经排序完成的数组，一般没有规律的数组，不建议使用
一般写法

1
2
3
4
5
6
7
8
9
10
11
left = 0 #初始化左边界
res = -float('inf') or float('inf') #初始化返回值
for right in len(nums):# while right <len(nums):   
    pass #更新窗口的内部信息

	while： #根据题意进行调整left，此时正在滑动left指针，使用while
    	# 比较更新res（用于收缩场景）
        pass # 扩张或者收缩窗口的大小

    # 比较更新res（用于扩张场景）
return res

左右指针

1
2
3
4
5
6
7
8
left, right = 0, len(nums) - 1 #初始化left，right
while left < right:
    if nums[left] + nums[right] > target: # 收缩right
        right -= 1
    elif nums[left] + nums[right] < target:# 扩张left
        left += 1
    elif nums[left] + nums[right] == target: # 返回结果
        return [left, right]

快慢指针
寻找列表中间的项

1
2
3
4
5
fast, slow = 0, 0
while fast < len(nums):
    slow += 1
    fast += 2
return nums(slow)

原地修改问题

原地修改问题一般使用双指针来解决，注意交换的顺序

删除有序数组中的重复项

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # 变动1: 由于元素可以重复2次，left现在从第二个元素开始，right从第三个元素开始
        left = 1
        for right in range(2, len(nums)):
            # 变动2: 以前之和nums[left]比, 现在还要和nums[left - 1]比，从而保证元素可以重复两次
            if nums[right] == nums[left] and nums[right] == nums[left - 1]:
                continue
            left += 1
            nums[left] = nums[right]
        return left + 1

删除有序数组中的重复项，此时允许有k次重复

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def removeDuplicates(self, nums: List[int], K: int) -> int:
        left = K - 1
        for right in range(K, len(nums)):
            tag = True
            for i in range(K):
                tag *= (nums[right] == nums[left - i])
            if tag:
                continue

            left += 1
            nums[left] = nums[right]
        return left + 1
[up主专用，视频内嵌代码贴在这]