leetcode数组双指针练习题

26. 删除有序数组中的重复项

如果允许额外开辟数组，可以遍历原数组，将不重复的元素依次存入新数组。但题目要求原地修改，所以这里使用快慢指针：slow 指向当前有效区间的末尾，fast 向后寻找新元素。遇到相同值就跳过，遇到不同值时先将 slow 加一，再把新元素写到该位置。例如数组为 1、1、2，两个指针初始都在索引 0；fast 走到 2 时，要保留第一个 1，并用 2 覆盖第二个 1。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow = 0
        fast = 0
        while fast < len(nums):
            if nums[fast] != nums[slow]:
                slow += 1
                nums[slow] = nums[fast]
            fast += 1
        return slow + 1

83. 删除排序链表中的重复元素

思路与第 26 题相同，只是数组赋值变成了修改链表指针。最后还要注意：如果 slow 不为空，需要把 slow.next 设为空，断开有效部分后面可能残留的节点。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head
        while fast != None:
            if fast.val != slow.val:
                slow.next = fast
                slow = slow.next
            fast = fast.next
        if slow != None:
            slow.next = None
        return head

这次 slow 表示下一个写入位置。fast 遇到不等于 val 的元素时，先写入 nums[slow]，再将 slow 加一。例如数组为 3、2、2、3，val 为 3，fast 走到索引 1 的 2 时，就用它覆盖索引 0 的 3。处理后，区间 [0, slow-1] 不包含 val，共有 slow 个元素，因此返回 slow。第 26 题的有效区间则是 [0, slow]，所以返回 slow+1。

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slow = 0
        fast = 0
        while fast < len(nums):
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow

283. 移动零

可以沿用第 27 题的思路，先把所有非零元素移到前面。但本题要求修改整个数组，而非只返回有效长度，所以还要把 slow 及其后面的剩余位置全部填成 0。

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        slow = 0
        fast = 0
        while fast < len(nums):
            if nums[fast] != 0:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        for i in range(slow, len(nums)):
            nums[i] = 0

167. 两数之和 II - 输入有序数组

暴力做法是枚举所有数对，检查两数之和是否等于 target，时间复杂度为 $O(n^2)$ 。利用数组有序这一条件，可以改用左右指针：left 从第一个元素出发，right 从最后一个元素出发。两数之和小于 target 时，将 left 右移；大于 target 时，将 right 左移；相等时返回两个位置。循环只在 left < right 时继续，避免重复使用同一个元素。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        left = 0
        right = len(nums) - 1
        while left < right:
            s = nums[left] + nums[right]
            if s < target:
                left += 1
            elif s > target:
                right -= 1
            else:
                return [left + 1, right + 1]

注意下标要求：代码中的数组索引从 0 开始，题目要求的位置从 1 开始，因此返回时两个索引都要加一。

344. 反转字符串

让左右指针分别指向字符串的首尾，交换对应字符后同时向中间移动。依次交换第一个与最后一个、第二个与倒数第二个字符，直到两个指针相遇或交错。

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        left = 0
        right = len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

5. 最长回文子串

回文串正着读和倒着读相同，例如“abcba”。可以枚举中心，从中心向两侧扩散，找到以这个位置为中心的最长回文串，再更新答案。

先写一个中心扩散函数。回文串的长度可能为奇数，也可能为偶数：left == right 表示以一个字符为中心，两个相邻位置则表示偶数长度的中心。循环退出时，左右指针已经走出有效回文范围，因此返回 left+1 到 right 之前的部分。

    def func(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1 : right]

完整代码中，依次枚举每个位置 i，分别检查以 i 为中心、以 i 和 i+1 为中心的回文串，并更新最长结果。func 中先检查边界，再比较字符，因此扩散到字符串两端时不会越界。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        res = ""
        for i in range(len(s)):
            s1 = self.func(s, i, i)
            s2 = self.func(s, i, i + 1)
            res = res if len(res) > len(s1) else s1
            res = res if len(res) > len(s2) else s2
        return res

    def func(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1 : right]