线性结构套路

def two_sum(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}            # 值 -> 该值出现的下标
    for i, x in enumerate(nums):
        need = target - x                # 要凑成 target，还差这个数
        if need in seen:                 # 这个差之前出现过 -> 找到一对
            return [seen[need], i]
        seen[x] = i                      # 没找到，把当前值登记进哈希表
    return []                            # 无解

print(two_sum([2, 7, 11, 15], 9))        # [0, 1]
print(two_sum([3, 2, 4], 6))             # [1, 2]

def two_sum_sorted(nums: list[int], target: int) -> list[int]:
    left, right = 0, len(nums) - 1       # 两端各放一个指针
    while left < right:
        s = nums[left] + nums[right]      # 当前两端之和
        if s == target:
            return [left, right]         # 命中
        elif s > target:
            right -= 1                    # 和太大，缩小：右指针左移
        else:
            left += 1                     # 和太小，增大：左指针右移
    return []                            # 无解

print(two_sum_sorted([2, 3, 5, 8, 11], 13))   # [0, 4]
print(two_sum_sorted([1, 2, 3, 4], 100))      # []

class ListNode:                          # 复用第 02 章的链表节点
    def __init__(self, val: int = 0, nxt: "ListNode | None" = None):
        self.val = val
        self.next = nxt

def has_cycle(head: ListNode | None) -> bool:
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next                 # 慢指针走一步
        fast = fast.next.next            # 快指针走两步
        if slow is fast:                 # 快指针追上慢指针 -> 有环
            return True
    return False                         # 走到 None -> 无环

# 构造 1 -> 2 -> 3 -> 2(回到第二个节点) 的环
a, b, c = ListNode(1), ListNode(2), ListNode(3)
a.next, b.next, c.next = b, c, b
print(has_cycle(a))                      # True
print(has_cycle(ListNode(1, ListNode(2))))   # False

def length_of_longest_substring(s: str) -> int:
    last: dict[str, int] = {}            # 字符 -> 最后一次出现的下标
    left = 0                             # 窗口左边界
    best = 0
    for right, ch in enumerate(s):       # right 单调扩张
        if ch in last and last[ch] >= left:
            left = last[ch] + 1          # 重复字符在窗口内 -> 收缩左边界到它之后
        last[ch] = right                 # 更新该字符最新位置
        best = max(best, right - left + 1)   # 当前窗口宽度
    return best

print(length_of_longest_substring("abcabcbb"))   # 3  ("abc")
print(length_of_longest_substring("bbbbb"))       # 1  ("b")
print(length_of_longest_substring("pwwkew"))       # 3  ("wke")

def subarray_sum(nums: list[int], k: int) -> int:
    count = 0
    cur = 0                              # 当前前缀和
    seen: dict[int, int] = {0: 1}        # 前缀和 -> 出现次数；空前缀和 0 先垫一个
    for x in nums:
        cur += x                         # 把当前元素累进前缀和
        need = cur - k                   # 若某个旧前缀和等于 need，二者之差就是 k
        count += seen.get(need, 0)       # 有几个这样的旧前缀和，就有几个子数组
        seen[cur] = seen.get(cur, 0) + 1 # 登记当前前缀和
    return count

print(subarray_sum([1, 1, 1], 2))        # 2
print(subarray_sum([1, 2, 3], 3))        # 2
print(subarray_sum([1, -1, 0], 0))       # 3