1.3 单序列双指针

2153字约7分钟

2024-11-15

1.3.1 相向双指针

提示

阿囧说：两个指针 left= 0，right=n-1，从数组的两端开始，向中间移动，这叫相向双指针，一般用于一个数变大一个数变小。上面的滑动窗口相当于同向双指针。一般会以while开头，内部再写两个while分别控制left右移和right左移，有点像快排。注意：三个while一般都要带上 left < right，避免指针越界

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

时间复杂度：O(n)

空间复杂度：O(1)

拓展一下，也可以使用递归来翻转字符串，不过本题要求在原地修改输入数组

def recursion(s):
if len(s) == 1:
    return s
else:
    return s[-1] + recursion(s[:-1])

s = "hello"
recursion(s)

输出：'olleh'

125. 验证回文串

class Solution:
def isPalindrome(self, s: str) -> bool:
    s = s.lower()
    left = 0
    right = len(s) - 1
    while left < right:
        while not s[left].isalnum() and left < right:
            left += 1
        while not s[right].isalnum() and left < right:
            right -= 1
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

时间复杂度：O(n)

空间复杂度：O(1)

1750. 删除字符串两端相同字符后的最短长度

class Solution:
def minimumLength(self, s: str) -> int:
    left = 0
    right = len(s) - 1
    while s[left] == s[right] and left < right:
        while s[left] == s[left+1] and left+1 < right:
            left += 1
        while s[right] == s[right-1] and left+1 < right:
            right -= 1
        left += 1
        right -= 1
    return max(0, right - left + 1)

时间复杂度：O(n)

空间复杂度：O(1)

2105. 给植物浇水 II

class Solution:
def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:
    left = 0
    right = len(plants) - 1
    a, b, res = capacityA, capacityB, 0
    while left < right:
        if a < plants[left]:
            a = capacityA
            res += 1
        if b < plants[right]:
            b = capacityB
            res += 1
        a -= plants[left]
        left += 1
        b -= plants[right]
        right -= 1
    if left == right and max(a, b) < plants[left]:
            res += 1
    return res

时间复杂度：O(n)

空间复杂度：O(1)

977. 有序数组的平方

相向双指针写法

class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
    left = 0
    right = len(nums) - 1
    temp = right
    res = [0] * len(nums)
    while left <= right:
        if abs(nums[left]) < abs(nums[right]):
            res[temp] = nums[right] ** 2
            right -= 1
        else:
            res[temp] = nums[left] ** 2
            left += 1
        temp -= 1
    return res

时间复杂度：O(n)

空间复杂度：O(n)

直接平方然后排序写法

class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
    for i, num in enumerate(nums):
        nums[i] = num ** 2
    return sorted(nums)

时间复杂度：O(nlogn)

空间复杂度：O(n)

658. 找到 K 个最接近的元素

class Solution:
def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:
    left = 0
    right = len(plants) - 1
    a, b, res = capacityA, capacityB, 0
    while left < right:
        if a < plants[left]:
            a = capacityA
            res += 1
        if b < plants[right]:
            b = capacityB
            res += 1
        a -= plants[left]
        left += 1
        b -= plants[right]
        right -= 1
    if left == right and max(a, b) < plants[left]:
            res += 1
    return res

时间复杂度：O(n)

空间复杂度：O(1)

1471. 数组中的 k 个最强值

class Solution:
def getStrongest(self, arr: List[int], k: int) -> List[int]:
    arr.sort()
    left = 0
    right = len(arr) - 1
    mid = (left + right) // 2
    arr[mid]
    res = []
    for i in range(k):
        if arr[right] - arr[mid] >= arr[mid] - arr[left]:
            res.append(arr[right])
            right -= 1
        else:
            res.append(arr[left])
            left += 1
    return res

时间复杂度：O(nlogn)

空间复杂度：O(n)

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

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

时间复杂度：O(n)

空间复杂度：O(1)

633. 平方数之和

直接用 right = c 会超时，应该使用 right = isqrt(c)，比如 18 开根号向下取整是 4 ，那么不可能有 $5^2$ 加上一个整数的平方等于18，所以右指针只用从 4 开始向左遍历即可

class Solution:
def judgeSquareSum(self, c: int) -> bool:
    left = 0
    right = isqrt(c)
    while left <= right:
        if left ** 2 + right ** 2 < c:
            left += 1
        elif left ** 2 + right ** 2 > c:
            right -= 1
        else:
            return True
    return False

时间复杂度：O( $\sqrt{c}$ )

空间复杂度：O(1)

2824. 统计和小于目标的下标对数目

枚举法

class Solution:
def countPairs(self, nums: List[int], target: int) -> int:
    n = len(nums)
    res = 0
    for i in range(n):
        for j in range(i+1, n):
            if nums[i] + nums[j] < target:
                res += 1
    return res

时间复杂度：O(n^2)

空间复杂度：O(1)

双指针法

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

时间复杂度：O(nlogn)

空间复杂度：O(1)

LCP 28. 采购方案

class Solution:
def purchasePlans(self, nums: List[int], target: int) -> int:
    left = 0
    right = len(nums) - 1
    res = 0
    nums.sort()
    while left < right:
        if nums[left] + nums[right] > target:
            right -= 1
        else:
            res += right - left
            left += 1
    return res%1000000007

时间复杂度：O(nlogn)

空间复杂度：O(1)

15. 三数之和

思路：排序复杂度为 O(nlogn)，使用三个指针 i j k ，把 i 固定住，j 和 k 相当于两数之和，i 用 for 循环复杂度为 O(n) ，j k 用相向双指针，也是 O(n) 的复杂度，故嵌套后的复杂度为 O( $n^2$ )，综合最后 O(nlogn) + O( $n^2$ ) = O( $n^2$ )

class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
    nums.sort()
    n = len(nums)
    res = []
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        j = i + 1
        k = n - 1
        while j < k:
            if nums[i] + nums[j] + nums[k] < 0:
                j += 1
            elif nums[i] + nums[j] + nums[k] > 0:
                k -= 1
            else:
                res.append([nums[i], nums[j], nums[k]])
                j += 1
                while nums[j] == nums[j - 1] and j < k:
                    j += 1
                k -= 1
                while nums[k] == nums[k + 1] and j < k:
                    k -= 1
    return res

时间复杂度：O( $n^2$ )

空间复杂度：O(1)

16. 最接近的三数之和

为了判断 sum_ijk 是不是与 target 最近的数，我们还需要用一个变量 min_ 维护 ∣s−target∣ 的最小值

class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
    nums.sort()
    n = len(nums)
    min_ = float('inf')
    for i in range(n - 2):
        j = i + 1
        k = n - 1
        while j < k:
            sum_ijk = nums[i] + nums[j] + nums[k]
            if sum_ijk > target:
                if sum_ijk - target < min_:
                    min_ = sum_ijk - target
                    res = sum_ijk
                k -= 1
            elif sum_ijk < target:
                if target - sum_ijk < min_:
                    min_ = target - sum_ijk
                    res = sum_ijk
                j += 1
            else:
                return target
    return res

时间复杂度：O( $n^2$ )

空间复杂度：O(1)

1.3.2 同向双指针

提示

两个指针的移动方向相同（都向右，或者都向左）。

581. 最短无序连续子数组

class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
    left, right = 0, -1
    # 从左向右确定右边界
    max_num = float('-inf')
    for i in range(len(nums)):
        if nums[i] >= max_num:
            max_num = nums[i]
        else:
            right = i
    # right没变意味着非递减
    if right == -1:
        return 0
    # 从右向左确定左边界
    min_num = float('inf')
    for i in range(len(nums) - 1, -1, -1):
        if nums[i] <= min_num:
            min_num = nums[i]
        else:
            left = i
    return right - left + 1

时间复杂度：O(n)

空间复杂度：O(1)

1.3.3 背向双指针

提示

两个指针从数组中的同一个位置出发，一个向左，另一个向右，背向移动。

1793. 好子数组的最大分数

class Solution:
def maximumScore(self, nums: List[int], k: int) -> int:
    left = right = k
    res = nums[k]
    min_num = nums[k]
    n = len(nums)
    for _ in range(n - 1):
        if right == n - 1 or left and nums[left - 1] > nums[right + 1]:
            left -= 1
            min_num = min(min_num, nums[left])
        else:
            right += 1
            min_num = min(min_num, nums[right])
        res = max(res, min_num * (right - left + 1))
    return res

时间复杂度：O(n)

空间复杂度：O(1)

1.3.4 原地修改

27. 移除元素

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

时间复杂度：O(n)

空间复杂度：O(1)

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

class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
    k = 1
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            continue
        nums[k] = nums[i]
        k += 1
    return k

时间复杂度：O(n)

空间复杂度：O(1)

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

需要用到双指针，有点小难

class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
    left = 2
    for right in range(2, len(nums)):
        if nums[right] != nums[left - 2]:
            nums[left] = nums[right]
            left += 1
    return left

时间复杂度：O(n)

空间复杂度：O(1)

283. 移动零

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

时间复杂度：O(n)

空间复杂度：O(1)