前言

本篇归纳双指针算法

• 快慢指针：主要是成环问题
• 左右指针：数组和字符串问题
• 滑动窗口：主要是子串问题

1、快慢指针

快慢指针
顾名思义
思路简单清晰
直接看下2个经典问题

链表是否有环

leet上141题

给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
如果 pos 是 -1，则在该链表中没有环。

快慢指针
如果有环，迟早会相遇

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        fast, slow = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow: return True
        return False

链表中有环，返回环的起始位置

leet上142题

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 
如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。

当快慢指针相遇时，让其中任⼀个指针指向头节点
然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        fast, slow = head, head
        while True:
            if not (fast and fast.next): return 
            fast, slow = fast.next.next, slow.next
            if fast == slow: break
        fast = head
        while fast != slow:
            fast, slow = fast.next, slow.next
        return fast

2、左右指针

通常在数组中

left = 0, right =len(nums) - 1

来看道题

最接近的三数之和

leet上第16题

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。
找出 nums 中的三个整数，使得它们的和与 target 最接近。
返回这三个数的和。假定每组输入只存在唯一答案。

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        res = float("inf")
        for i in range(len(nums)-1):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l, r = i + 1, len(nums) - 1
            while l < r:
                cur = nums[i] + nums[l] + nums[r]
                if cur == target: return target
                if abs(res - target) > abs(cur - target):
                    res = cur
                if cur > target:
                    r -= 1
                elif cur <= target:
                    l += 1
        return res

3、滑动窗口

思路简单
维护⼀个窗⼝，不断滑动，然后更新答案

下面看几道经典题

无重复字符的最长子串

leet上第3题

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:return 0
        left = 0
        lookup = set()
        n = len(s)
        max_len = 0
        cur_len = 0
        for i in range(n):
            cur_len += 1
            while s[i] in lookup:
                lookup.remove(s[left])
                left += 1
                cur_len -= 1
            if cur_len > max_len:max_len = cur_len
            lookup.add(s[i])
        return max_len

最小覆盖子串

leet上76题

给你一个字符串 S、一个字符串 T 。
请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or len(s) < len(t): return ""
        from collections import Counter
        t = Counter(t)
        lookup = Counter()
        start, end = 0, 0
        min_len = float("inf")
        res = ""
        while end < len(s):
            lookup[s[end]] += 1
            end += 1
            while all(map(lambda x: lookup[x] >= t[x], t.keys())):
                if end - start < min_len:
                    res = s[start:end]
                    min_len = end - start
                lookup[s[start]] -= 1
                start += 1
        return res

至多包含 K 个不同字符的最长子串

leet上340题

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        from collections import defaultdict
        lookup = defaultdict(int)
        start = 0
        end = 0
        max_len = 0
        counter = 0
        while end < len(s):
            if lookup[s[end]] == 0:
                counter += 1
            lookup[s[end]] += 1
            end += 1
            while counter > k:
                if lookup[s[start]] == 1:
                    counter -= 1
                lookup[s[start]] -= 1
                start += 1
            max_len = max(max_len, end - start)
        return max_len

结语

双指针算法思路简单清晰
就是边界条件需要思考下

最后

以上就是忐忑煎饼为你收集整理的算法系列：双指针——快慢指针、左右指针、滑动窗口前言结语的全部内容，希望文章能够帮你解决算法系列：双指针——快慢指针、左右指针、滑动窗口前言结语所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。