双指针（双指针遍历数组）

双指针（双指针遍历数组）

1. 相向双指针

Reverse 型：翻转字符串、判断回文串 Two Sum 型：两数之和、三数之和 Partition 型：快速排序、颜色排序

框架

def isPalindrome(s): # 一左一右两个指针（索引），分别从中间开始移动 left, right = 0, len(s) - 1 # left 一定要小于 right while left < right: if s[left] != s[right]: return False left += 1 # left 向右移动一位 right -= 1 # right 向左移动一位 return True

1.1 验证回文串

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。 说明：本题中，我们将空字符串定义为有效的回文串。 示例 1: 输入: "A man, a plan, a canal: Panama" 输出: true 解释："amanaplanacanalpanama" 是回文串 示例 2: 输入: "race a car" 输出: false 解释："raceacar" 不是回文串   提示： 1 <= s.length <= 2 * 105 字符串 s 由 ASCII 字符组成

题解：

class Solution: def isPalindrome(self, s: str) -> bool: good = "".join([i.lower() for i in s if i.isdigit() or i.isalpha()]) left, right = 0, len(good) - 1 while left < right: if good[left] != good[right]: return False left += 1 right -= 1 return True

1.2 验证回文串 II

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。 示例 1: 输入: s = "aba" 输出: true 示例 2: 输入: s = "abca" 输出: true 解释: 你可以删除c字符。 示例 3: 输入: s = "abc" 输出: false   提示: 1 <= s.length <= 105 s 由小写英文字母组成

题解：

class Solution: def validPalindrome(self, s: str) -> bool: if len(s) == 1: return True l, r = 0, len(s) - 1 while l < r: if s[l] == s[r]: l += 1 r -= 1 else: return self.is_palindrome(s, l+1, r) or self.is_palindrome(s, l, r-1) return True def is_palindrome(self, s, l, r): while l < r: if s[l] != s[r]: return False l += 1 r -= 1 return True

1.3 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 示例 1： 输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。 示例 2： 输入：nums = [3,2,4], target = 6 输出：[1,2] 示例 3： 输入：nums = [3,3], target = 6 输出：[0,1]   提示： 2 <= nums.length <= 104 -109 <= nums[i] <= 109 -109 <= target <= 109 只会存在一个有效答案

题解一：哈希表（时间、空间复杂度都为 O(n)）

class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: info = {} for index, i in enumerate(nums): if target - i in info: return [info[target -i], index] if i not in info: info[i] = index return [-1, -1]

题解二：排序 + 双指针（时间复杂度 O(nlogn)、空间复杂度 O(1)）

class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: num_idx = [(num, i) for i, num in enumerate(nums)] num_idx.sort(key=lambda x: x[0]) # [(2, 0), (7, 1), (11, 2), (15, 3)] left, right = 0, len(nums) - 1 while left < right: if num_idx[left][0] + num_idx[right][0] == target: return [num_idx[left][1], num_idx[right][1]] elif num_idx[left][0] + num_idx[right][0] > target: right -= 1 else: left += 1 return [-1, -1]

1.4 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 示例 1: 输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4 示例 2: 输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1   提示： 你可以假设 nums 中的所有元素是不重复的。 n 将在 [1, 10000]之间。 nums 的每个元素都将在 [-9999, 9999]之间。

题解：

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

1.5 反转数组

from typing import List class Solution: def reverse_list(self, nums: List[str]) -> List[str]: left, right = 0, len(nums) - 1 while left < right: temp = nums[left] nums[left] = nums[right] # 左右两个数进行交换 nums[right] = temp right -= 1 left += 1 return nums if __name__ == '__main__': s = Solution() print(s.reverse_list(["1", "2", "3"])) print(s.reverse_list(["3", "2", "1"]))

分析：

nums = ["1", "2", "3"] # 第一次 left = 0, right = 2 while 0 < 2: temp = "1" nums[0] = nums[2] => nums = ["3", "2", "3"] nums[2] = "1" => nums = ["3", "2", "1"] right -= 1 left += 1 # 第二次 left = 1, right = 1 while 1 < 1: return nums

1.6 判断字符串回文

def solution(string): left, right = 0, len(string) - 1 while left < right: if string[left] != string[right]: return False left += 1 right -= 1 return True if __name__ == '__main__': print(solution("aba")) print(solution("abac")) print(solution("1221"))

2. 背向双指针

2.1 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。 示例 1： 输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。 示例 2： 输入：s = "cbbd"

题解：

技巧：从中心向两端扩散的双指针技巧

因为回文串长度有可能是奇数，也有可能是偶数；如果是奇数时，可以以中间字符作为分割点向两端扩散，若是偶数时，则可以中心两个字符往外扩散：

class Solution: def longestPalindrome(self, s: str) -> str: long_sub = "" for i in range(len(s)): s1 = is_palindrome(s, i, i) # 以 s[i] 为中心的最长回文子串 s2 = is_palindrome(s, i, i+1) # 以 s[i] 和 s[i+1] 为中心的最长回文子串 long_sub = long_sub if len(long_sub) > len(s1) else s1 long_sub = long_sub if len(long_sub) > len(s2) else s2 return long_sub def is_palindrome(s, l, r): """ 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串 """ # 防止下标越界 while l >= 0 and r < len(s): if s[l] != s[r]: break # 双指针，向两边展开 l -= 1 r += 1 return s[l+1: r] # 返回以 s[l] 和 s[r] 为中心的最长回文串

3. 同向双指针

同向双指针也称作快慢指针

3.1 删除有序数组重复项

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。 由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。 将最终结果插入 nums 的前 k 个位置后返回 k 。 不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成 示例 1： 输入：nums = [1,1,2] 输出：2, nums = [1,2,_] 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。 示例 2： 输入：nums = [0,0,1,1,1,2,2,3,3,4] 输出：5, nums = [0,1,2,3,4] 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

题解：

from typing import List class Solution: def removeDuplicates(self, nums: List[int]) -> int: if len(nums) == 0: return 0 slow, fast = 0, 0 print(nums, slow, fast) while fast < len(nums): if nums[fast] != nums[slow]: slow += 1 nums[slow] = nums[fast] fast += 1 print(nums, slow, fast) return slow + 1 if __name__ == '__main__': s = Solution() print(s.removeDuplicates([1, 1, 2, 3])) # 3 print(s.removeDuplicates([0, 0, 1, 1, 2, 3, 4, 5, 6])) # 7

[1, 1, 2, 3] 0 0 [1, 1, 2, 3] 0 1 [1, 1, 2, 3] 0 2 [1, 2, 2, 3] 1 3 [1, 2, 3, 3] 2 4

slow 慢指针走在后面，fast 快指针走在前面，遇到不重复的元素就赋值给 slow，并 slow 前进一步，这样 nums[0, slow] 就是不重复的元素

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

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

输入：head = [1,1,2] 输出：[1,2] 输入：head = [1,1,2,3,3] 输出：[1,2,3]

题解：

# 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: ListNode) -> ListNode: if head == None: return None slow = fast = head while fast != None: if fast.val != slow.val: slow.next = fast slow = slow.next fast = fast.next slow.next = None # 断开与后面重复元素的连接 return head

3.3 移除数组中指定元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1： 输入：nums = [3,2,2,3], val = 3 输出：2, nums = [2,2] 解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。 示例 2： 输入：nums = [0,1,2,2,3,0,4,2], val = 2 输出：5, nums = [0,1,4,0,3] 解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

题解：

from typing import List class Solution: def removeElement(self, nums: List[int], val: int) -> int: if not nums: return 0 slow, fast = 0, 0 print(f"nums: {nums}\tslow: {slow}\tfast: {fast}\tval: {val}") while fast < len(nums): if nums[fast] != val: nums[slow] = nums[fast] slow += 1 fast += 1 print(f"nums: {nums}\tslow: {slow}\tfast: {fast}\tval: {val}") return slow if __name__ == '__main__': s = Solution() # print(s.removeElement([0, 1, 2, 2, 3, 0, 4, 2], 2)) print(s.removeElement([0, 1, 2], 0)) # 2

nums: [0, 1, 2] slow: 0 fast: 0 val: 0 nums: [0, 1, 2] slow: 0 fast: 1 val: 0 nums: [1, 1, 2] slow: 1 fast: 2 val: 0 nums: [1, 2, 2] slow: 2 fast: 3 val: 0

fast 所在元素与 val 相同则跳过该元素，fast + 1 fast 所在元素与 val 不同时，将当前元素赋值给 slow， slow 前进 1

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。