算法总结-双指针技巧

介绍#

双指针技巧，是一种处理数组和链表相关问题经常用到的技巧。其中，最常用到的无非两种：左右指针和快慢指针。

相向双指针#

当数组有序，需要从两端逼近的时候，就可以想到相向双指针。核心特征是我们每次根据条件淘汰一侧，并且不回头

LC167 - 两数之和II#

我们假设两个指针的和已经大于target了，如果移动小的那头，那只会更大于，只有移动大的那头才能保证接下来可能出现两数之和。

Python3 点击展开代码

17 lines 展开代码

import ast

def solution(nums:list,target:int)->int:
    left, right = 0,len(nums)-1
    while left<right:
        if nums[left]+nums[right] == target:
            return [left+1,right+1]
        elif nums[left]+nums[right] < target:
            left+=1
        else:
            right-=1
            

if __name__ == "__main__":
    nums = ast.literal_eval(input().strip())
    target = int(input().strip())
    print(solution(nums,target))

LC11 - 盛最多水的容器#

思维方式类似。移动长边一定会减少水量，只有移动短边才可能会增多水量，所以我们要不断移动短边。

Python3 点击展开代码

16 lines 展开代码

import ast

def solution(height:list)->int:
    left, right = 0, len(height)- 1
    max_pool = 0
    while left<right:
        max_pool = max(max_pool,(right - left)*min(height[left],height[right]))
        if height[left]<height[right]:
            left += 1
        else:
            right -= 1 
    return max_pool

if __name__ == "__main__":
    height = ast.literal_eval(input().strip())
    print(solution(height))

LC125 - 验证回文串#

给一个句子，删除空格转小写拼接后，判断是否回文。思路很简单，注意python处理清洗就行。

Python3 点击展开代码

23 lines 展开代码

import ast

def solution(s:str)->bool:
    if not s:
        return True
    left, right = 0, len(s)-1
    while left<right:
        if s[left]!=s[right]:
            return False
        else:
            left+=1
            right-=1
        return True

if __name__ == "__main__":
    s = input().strip()
    s_list = []
    for c in s:
        if c.isalnum():
            s_list.append(c.lower())

    s_new = "".join(s_list)
    print(solution(s_new))

LC680 - 验证回文串II#

本题也就是由于允许一次试错，立刻想到回溯一下

Python3 点击展开代码

19 lines 展开代码

import ast

# 判断i,j之间的是否是回文串
def solution(i:int,j:int,s:str,flag:int)->bool:
    if i == j:
        return True
    while i<j:
        if s[i]!=s[j] and flag == 0:
            return solution(i+1,j,s,1)or solution(i,j-1,s,1)
        elif s[i]!=s[j] and flag == 1:
            return False
        else:
            i+=1
            j-=1
    return True  

if __name__ == "__main__":
    s = input().strip()
    print(solution(0,len(s)-1,s,0))

LC344 - 反转字符串#

除了字符输入处理倒是没什么可注意的。

Python3 点击展开代码

12 lines 展开代码

def solution(s: list[str]) -> list[str]:
    left, right = 0, len(s)-1
    while left<right:
        s[left],s[right] = s[right],s[left]
        left += 1
        right -= 1
    return s

if __name__ == "__main__":
    # 注意这里的输入
    s = [x.strip().strip('"').strip("'") for x in input().split(',')]
    print(solution(s))

LC881 - 救生艇#

这题就稍微有难度一点了，要用到贪心的思想。我们先把people按体重排好队，能用最多船的理想方案肯定是轻重搭配，后面按照双指针做就行了。

Python3 点击展开代码

20 lines 展开代码

import ast

def solution(people, limit):
    people.sort()
    left, right = 0, len(people) - 1
    count = 0

    while left <= right:
        if people[left] + people[right] <= limit:
            left += 1
        right -= 1
        count += 1

    return count


if __name__ == "__main__":
    people = ast.literal_eval(input().strip())
    limit = int(input().strip())
    print(solution(people,limit))

同向双指针#

同向双指针，其实就是滑动窗口。我们什么时候去使用它。

LC3 - 无重复字符的最长子串#

我们需要判断窗口的要素，是元素个数，这是一个与位置无关的属性，因此我们首先想到的就是滑动窗口。

Python3 点击展开代码

18 lines 展开代码

def solution(s:str):
    window = {}
    left , right = 0, 0
    max_len = 0
    while right<len(s):
        c = s[right]
        right += 1
        window[c] = window.get(c,0)+1
        while window[c]>1:
            c2 = s[left]
            left += 1
            window[c2] -= 1
        max_len = max(max_len,right-left)
    return max_len

if __name__ == "__main__":
    s = input().strip()
    print(solution(s))

LC209 - 长度最小的子数组#

依旧是满足一个条件的连续序列，条件与位置无关，按照标准滑动窗口思路。

Python3 点击展开代码

21 lines 展开代码

import ast

def solution(target:int,nums:list):
    total = 0
    left,right = 0, 0
    min_len = float('inf')
    while right<len(nums):
        c = nums[right]
        right += 1 
        total += c
        while total>=target:
            # 先判断长度
            min_len = min(min_len,right-left)
            total -= nums[left]
            left += 1
    return min_len if min_len!=float('inf') else 0

if __name__ == "__main__":
    target = int(input().strip())
    nums = ast.literal_eval(input().strip())
    print(solution(target,nums))

LC76 - 最小覆盖子串#

Python3 点击展开代码

33 lines 展开代码

import ast

def solution(s:str,t:str)->str:
    window, need = {},{}
    valid = 0
    min_len = float('inf')
    ans = ""
    for c in t:
        need[c] = need.get(c,0) + 1
    left, right = 0, 0 
    while right< len(s):
        c = s[right]
        right += 1
        if c in need:
            window[c] = window.get(c,0)+1
            if window[c] == need[c]:
                valid += 1
        while valid == len(need):
            if right - left < min_len:
                ans  = s[left:right]
                min_len = right - left
            c1 = s[left]
            left += 1
            if c1 in need:
                if window[c1] == need[c1]:
                    valid -= 1
                window[c1] -= 1
    return ans

if __name__ == "__main__":
    s = input().strip()
    t = input().strip()
    print(solution(s,t))

LC438 - 找到字符串中所有字母异位词#

这道题和前面的题目不一样，是固定窗口的滑动窗口题目。注意一下收缩valid的控制只有一种写法（先判断，再扣window）就行：

Python3 点击展开代码

31 lines 展开代码

import ast

def solution(s:str,p:str)->list:
    window , need = {}, {}
    left, right =0, 0
    ans = []
    valid = 0
    for c in p:
        need[c] = need.get(c,0) + 1
    while right<len(s):
        c1 = s[right]
        right += 1
        if c1 in need:
            window[c1] = window.get(c1,0) + 1
            if window[c1] == need[c1]:
                valid += 1
        while right - left > len(p):
            c2 = s[left]
            left += 1
            if c2 in need:
                if window[c2] == need[c2]:
                    valid -= 1
                window[c2] -= 1
        if valid == len(need):
            ans.append(left)
    return ans

if __name__ == "__main__":
    s = input().strip()
    p = input().strip()
    print(solution(s,p))

LC567 - 字符串的排列#

跟上题一样，是固定窗口滑动.

Python3 点击展开代码

31 lines 展开代码

import ast

def solution(s1:str,s2:str)->list:
    window, need = {}, {}
    valid = 0
    for c in s1:
        need[c] = need.get(c,0) + 1
    left, right = 0, 0
    while right<len(s2):
        c1 = s2[right]
        right += 1
        if c1 in need:
            window[c1] = window.get(c1,0) + 1
            if window[c1] == need[c1]:
                valid += 1
        while right - left > len(s1):
            c2 = s2[left]
            left += 1
            if c2 in need:
                if window[c2] == need[c2]:
                    valid -= 1
                window[c2] -= 1
        # 如果包含，就可以返回了
        if valid == len(need):
            return True
    return False

if __name__ == "__main__":
    s1 = input().strip()
    s2 = input().strip()
    print(solution(s1,s2))

LC904 - 水果成篮#

这一题，实际上是在求，满足窗口里面只有两种数字的最大连续窗口长度。但是本题有一个很关键的点，就是window[c] 回退到0的时候，key还是存在的，这样会扰乱 if not in window这样的语句，所以到0的话我们需要用del删除这个键（之前为什么不用呢，因为前面关心的主要是window和need的技术关系，和valid维持满足要求的字符种类数，而不关心len(window)）

Python3 点击展开代码

30 lines 展开代码

import ast

def solution(fruits:list)->int:
    max_len = 0
    type = 0
    window = {}
    left, right = 0, 0
    while right<len(fruits):
        c1 = fruits[right]
        right += 1
        if c1 not in window:
            type += 1
        window[c1] = window.get(c1,0) + 1
        while type > 2:
            c2 = fruits[left]
            left += 1
            if c2 in window:
                window[c2] -= 1
                if window[c2] == 0:
                    type -= 1
                    # 删除很关键
                    del window[c2]
                
        # 种类正好两种
        max_len = max(max_len,right - left)
    return max_len

if __name__ == "__main__":
    fruits = ast.literal_eval(input().strip())
    print(solution(fruits))

另外，其实这题不用维持type了，len(window)本身当做指标，可以让代码更简洁容易：

Python3 点击展开代码

18 lines 展开代码

def solution(fruits: list[int]) -> int:
    window = {}
    left = 0
    max_len = 0

    for right, fruit in enumerate(fruits):
        window[fruit] = window.get(fruit, 0) + 1

        while len(window) > 2:
            left_fruit = fruits[left]
            window[left_fruit] -= 1
            if window[left_fruit] == 0:
                del window[left_fruit]
            left += 1

        max_len = max(max_len, right - left + 1)

    return max_len

LC1004 - 最大连续1的个数III#

这一题要是没有最多翻转k个0这事，就可以直接统计了。有了这个条件后，实际上可以转化成滑动窗口来做，用0的数目（也就是k）来当做窗口需要考虑的属性。

Python3 点击展开代码

30 lines 展开代码

import ast

def solution(nums:list,k:int)->int:
    # 统计0、1的数目
    count_1 = 0
    count_0 = 0
    max_len = 0 
    left, right = 0, 0
    while right < len(nums):
        c1 = nums[right]
        right += 1
        if c1 == 1:
            count_1 += 1
        else:
            count_0 += 1
        while count_0 > k:
            c2 = nums[left]
            left += 1
            if c2 == 1:
                count_1 -= 1
            else:
                count_0 -= 1
        max_len = max(max_len,right - left)
    return max_len


if __name__ == "__main__":
    nums = ast.literal_eval(input().strip())
    k = int(input().strip())
    print(solution(nums,k))

LC713 - 乘积小于K的子数组#

需要注意的地方都写在题目里了。滑动窗口要避免一直缩窗的情况出现。

Python3 点击展开代码

26 lines 展开代码

import ast

def solution(nums:list,k:int)->int:
    # 避免一直推窗
    if k<=1:
        return 0
    # 全都是正数，直接滑动
    curr = 1
    left, right = 0, 0
    count = 0
    while right<len(nums):
        c1 = nums[right]
        right += 1
        curr *= c1
        while curr >= k:
            c2 = nums[left]
            left += 1
            curr //= c2
        # 当右端点固定在 right - 1 时，当前窗口 [left, right) 的乘积 < k 就合格，换句话说就是所有以 right - 1 结尾、起点在 left ... right - 1 的子数组都合法，也就是有right - left个
        count += (right-left)
    return count

if __name__ == "__main__":
    nums = ast.literal_eval(input().strip())
    k = int(input().strip())
    print(solution(nums,k))

快慢指针#

快慢指针式链表、数组的经典题目，代表的三类用法，处理环形、做尺子丈量和找出中点。第一种要记住141、142的结论，第二种是倒数第k个节点的无额外空间解，第三个找中点最常用，就是奇偶容易错，建议脑补一下3、4两种节点。

LC141 - 环形链表#

Python3 点击展开代码

38 lines 展开代码

# 本题也是经典结论，fast走两步，slow走一步，最终如果相遇则有环
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 这里升级了一下，直接返回头指针+节点列表
def build_linked_list(nums):
    dummy = ListNode()
    cur = dummy
    nodes = []
    for x in nums:
        cur.next = ListNode(x)
        cur = cur.next
        nodes.append(cur)
    return dummy.next, nodes

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

if __name__ == "__main__":
    nums_line = input().strip()
    pos = int(input().strip())

    # 注意这里有个判空逻辑
    nums = list(map(int, nums_line.split(','))) if nums_line else []
    head, nodes = build_linked_list(nums)

    if pos != -1 and nodes:
        nodes[-1].next = nodes[pos]

    print(solution(head))

或者这样写：

Python3 点击展开代码

11 lines 展开代码

def hasCycle(self, head: Optional[ListNode]) -> bool:
    if not head or not head.next:
        return False
    slow = head
    fast = head.next
    while fast != slow:
        if not fast or not fast.next:
            return False
        slow = slow.next
        fast = fast.next.next
    return True

这种写法有点别扭，一般推荐第一种写法。我们做一点推广，这种判环的最简单写法，归根结底，其实就是这样的模版：

Python3 点击展开代码

7 lines 展开代码

slow = start
fast = start # 或者fast先走一格，一旦next就要判断会不会None.next
while 没有到达“无环结束条件”:
    slow = next(slow)
    fast = next(next(fast))
    if slow == fast:
        说明有环

LC142 - 环形链表II#

Python3 点击展开代码

20 lines 展开代码

class ListNode:
    def __init__(self,val = 0,next = None):
        self.val = val
        self.next = next

def solution(self,head:ListNode)->bool:
    fast, slow = head,head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if fast == slow:
            break
    # 无环返回
    if not fast or not fast.next:
        return None
    start = head
    while start != slow:
        start = start.next
        slow = slow.next
    return start

LC876 - 链表的中间结点#

来到了快慢链表题，这类题目要注意奇偶的情况，本题要求偶数后半或者奇数中点。

Python3 点击展开代码

6 lines 展开代码

def solution(head:ListNode)->bool:
    fast, slow = head,head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
    return slow

拓展：如果是偶数前半呢？答案是让fast的判断范围往前一步，这样就可以早停slow：

Python3 点击展开代码

6 lines 展开代码

def solution(head:ListNode)->bool:
    fast, slow = head,head
    while fast.next and fast.next.next:
        fast = fast.next.next
        slow = slow.next
    return slow

拓展：部分题目中，我们可能需要删除头结点，这样就必须要让fast和slow从dummy开始，否则操作就会不统一，很别扭。

那么，带dummy的找中点前一位，偶数前半，操作其实和之前类似：

Python3 点击展开代码

5 lines 展开代码

dummy = ListNode(0, head)
fast, slow = dummy, dummy
while fast.next and fast.next.next:
    fast = fast.next.next
    slow = slow.next

但是此时，slow会停在中点前面的一个合适位置。对于奇数，会返回slow中点前一个节点，偶数会返回前半，这是为了方便切半链表做进一步判断。

同样，如下写法，是找中点，偶数前半：

Python3 点击展开代码

5 lines 展开代码

dummy = ListNode(0, head)
fast, slow = dummy, dummy
while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

注意，带dummy的两种写法都是偶数前半，区别只是找到中点还是中点前一位。所以，这一题，如果我们写如下的代码也可以通过：

Python3 点击展开代码

7 lines 展开代码

def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        fast, slow = dummy, dummy
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        return slow.next

最后还可以补充一句，其实我们可以直接通过fast最终的位置判断奇偶，比如无dummy，while fast and fast.next，如果fast最后停在None，那就是偶数，否则是奇数。其他的跳法脑补一下3、4个结点的情况。

LC19 - 删除链表的倒数第N个结点#

这是拿fast和slow当尺子，测倒数第N个结点的方法，方法是让fast先走N步，然后同步前进。由于可能会删除头结点，因此需要dummy。

我们需要停在待删除节点的前一位，可以在脑海中想象一下。所以我们要用fast.next来判断：

Python3 点击展开代码

10 lines 展开代码

def solution(head:ListNode,n:int)->bool:
    dummy = ListNode(0,head)
    p,q = dummy,dummy
    for _ in range(n):
        q = q.next
    while q.next:
        p = p.next
        q = q.next
    p.next = p.next.next
    return dummy.next

LC202 - 快乐数#

这题乍一看和双指针没关系，直接用循环和set解决：

Python3 点击展开代码

32 lines 展开代码

class ListNode:
    def __init__(self,val = 0,next = None):
        self.val = val
        self.next = next

def solution(n:int)->bool:
    # 不断计算，如果遇到出现过的数字，那么就是无限循环
    if n == 0:
        return False
    seen = set()
    seen.add(0)
    total = 0
    while n:
        mod = n%10
        total += mod*mod
        n = int(n/10)
    while total not in seen:
        seen.add(total)
        now = 0
        while total:
            mod = total%10
            now += mod*mod
            total = int(total/10)
        if now == 1:
            return True
        else:
            total = now
    return False

if __name__ == "__main__":
    n = int(input().strip())
    print(solution(n))

但是实际上，这题可以抽象成一个Floyd快慢指针题，本质是在"不断跳到下一个状态"的过程中判断有没有环。我们可以写法变成如下：

Python3 点击展开代码

21 lines 展开代码

def get_next(n: int) -> int:
    total = 0
    while n > 0:
        digit = n % 10
        total += digit * digit
        n //= 10
    return total

def solution(n: int) -> bool:
    slow = n
    fast = get_next(n)

    while fast != 1 and slow != fast:
        slow = get_next(slow)
        fast = get_next(get_next(fast))

    return fast == 1

if __name__ == "__main__":
    n = int(input().strip())
    print(solution(n))

Floyd快慢指针法的空间复杂度为O(1)，非常巧妙。

不过我们可以注意到，在这种逻辑判环中，我们不能用fast的位置来判断有没有环，所以我们需要更新一下条件。

然后额外注意要用 fast != slow 时，要让他们起点不一样，不然直接都不循环了。

LC287 - 寻找重复数#

同样这题利用下标就可以了，不断将1-n搬到对应的0到n-1位置上，如果已经有了就重复。也就是说这题本来的做法是原地哈希：

Python3 点击展开代码

13 lines 展开代码

def solution(nums: list[int]) -> int:
    i = 0
    while i < len(nums):
        # 当前位置已经是正确数了才调整位置
        if nums[i] == i + 1:
            i += 1
            continue

        correct_idx = nums[i] - 1
        if nums[correct_idx] == nums[i]:
            return nums[i]

        nums[i], nums[correct_idx] = nums[correct_idx], nums[i]

经过前面的几题，你应该知道了这题可以抽象成Floyd环，因为数组长度是 n+1，值域是 [1, n]，说明一定有重复，重复就会导致"指向同一个位置"，于是形成环。得出代码如下：

Python3 点击展开代码

16 lines 展开代码

def solution(nums: list[int]) -> int:
    slow = nums[0]
    fast = nums[0]

    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

    return slow

这实际上就是把寻找环位置值的代码抽象了出来。它同时满足不修改数组和额外空间O(1)，是比原地哈希更好的方法。

读写双指针#

读写双指针，是用一根遍历，一根更新的技巧。

LC26 - 删除有序数组中的重复项#

Python3 点击展开代码

14 lines 展开代码

def removeDuplicates(self, nums: List[int]) -> int:
    # 删除非严格递增的数组nums，删除重复元素，返回唯一元素个数
    # 两个指针解决问题
    if not nums:
        return 0
    slow = 1
    # 快指针
    for fast in range(1,len(nums)):
        if nums[fast]!=nums[fast-1]:
            # 遇到不一样的搬过来
            nums[slow]=nums[fast]
            slow+=1
    # 慢指针的位置就是所有独一无二的元素长度
    return slow

有一点要注意，这里让fast从1开始是为了不让fast-1越界，并且根据往后看了一格，也全部判断到了。fast还是从0开始比较多，比如写成这样（依旧要判断右边越界）：

Python3 点击展开代码

10 lines 展开代码

def removeDuplicates(self, nums: List[int]) -> int:
        i,j = 0,0 
        while j<len(nums):
            if j+1<len(nums) and nums[j] == nums[j+1]:
                j+=1
                continue
            nums[i] = nums[j]
            i+=1
            j+=1
        return i

LC27 - 移除元素#

跟上一题只是判断条件不同，依然是公式写法：

Python3 点击展开代码

10 lines 展开代码

def removeElement(self, nums: list[int], val: int) -> int:
    p,q = 0,0
    while q<len(nums):
        if nums[q] == val:
            q+=1
            continue
        nums[p] = nums[q]
        p+=1
        q+=1
    return p

LC80 - 删除有序数组中的重复项II#

由于是有序数组，本题其实只是比LC26多一位判断：

Python3 点击展开代码

10 lines 展开代码

def removeDuplicates(self, nums: list[int]) -> int:
    i,j = 0,0 
    while j<len(nums):
        if j+2<len(nums) and nums[j] == nums[j+1] == nums[j+2]:
            j+=1
            continue
        nums[i] = nums[j]
        i+=1
        j+=1
    return i

LC283 - 移动零#

也就是将所有非0元素保留，然后p继续移动置0即可。

Python3 点击展开代码

10 lines 展开代码

def moveZeroes(self, nums: list[int]) -> None:
    i,j = 0, 0
    while j<len(nums):
        if nums[j]!= 0:
            nums[i] = nums[j]
            i+=1
        j+=1
    while i<len(nums):
        nums[i] = 0
        i+=1

这里要注意一个点，非零元素不用在条件里面j+=1，因为j一定要移动的，就直接放最后面统一加，否则会移动两次。要不然，就在条件里面写一个continue，和之前一样。

LC75 - 颜色分类#

上面很多题，都是直接覆盖，因为不会丢信息，比如移动0只会覆盖0，后面补0就行；重复元素更不用说，有序重复时才覆盖，覆盖不会丢数字。但是这一题，不允许提前排序，如果还覆盖来写，就会丢信息，所以我们要改为交换元素而不是覆盖元素！

另外还有一个要注意的点，由于我们只是交换元素，所以不能让还没检查过的元素被跳过。尤其是遇到2时，从右侧换回来的元素还不知道是什么，可能还需要继续被判断一次（比如0原本在末尾，被换到了中间，还需要再换到开头）。

Python3 点击展开代码

22 lines 展开代码

import ast

def sortColors(nums: list[int]) -> None:
    # 由于只有三种元素，所以我们遍历将0放前面，2放后面，中间的自然就是1啦
    i,j,k = 0,0,len(nums)-1
    # 注意这里的循环条件有变化！
    while j <= k:
        if nums[j]==0:
            nums[i],nums[j] = nums[j],nums[i]
            i+=1
            j+=1
        elif nums[j]==2:
            nums[k],nums[j] = nums[j],nums[k]
            # 不确定是否还要移动到开头，所以j先不动，等待下次循环再检查是不是0
            k-=1
        else:
            j+=1

if __name__ == "__main__":
    nums = ast.literal_eval(input().strip())
    sortColors(nums)
    print(nums)

本题是大名鼎鼎的荷兰国旗问题，用双指针划分出三个区域。有几处是需要注意的。可以好好看看。

归并型双指针#

这种题目常见于链表，一边一个指针，不断将符合条件的加入新结构（也可能是原地）。我们往往需要新指针p来指引新位置。

LC88 - 合并两个有序数组#

这一题的关键是原地合并，nums1后面已经天然给出空位，我们可以直接从大到小从后往前填。

Python3 点击展开代码

13 lines 展开代码

def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
    p1 = m - 1
    p2 = n - 1
    p = m + n - 1

    while p2 >= 0:
        if p1 >= 0 and nums1[p1] > nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
        p -= 1

顺便拓展一下，如果nums1后面没有空位，我们就需要新结构，用非常简单的双指针逐位判断即可，注意走完之后要将结构加在后面：

Python3 点击展开代码

15 lines 展开代码

def merge(nums1: list[int], nums2: list[int]) -> list[int]:
    i, j = 0, 0
    ans = []

    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            ans.append(nums1[i])
            i += 1
        else:
            ans.append(nums2[j])
            j += 1

    ans.extend(nums1[i:])
    ans.extend(nums2[j:])
    return ans

当然，也可以用递归的方法。其实，归并双指针问题大多数都可以写成递归，这种递归本质还是双指针，只不过把移动指针的过程交给递归调用。（这种传下标的dfs倒是在需要知道所有情况方便回溯的时候常用，这种情况不太常用）。

Python3 点击展开代码

20 lines 展开代码

def merge(nums1: list[int], nums2: list[int]) -> list[int]:
    ans = []

    def dfs(i: int, j: int) -> None:
        if i == len(nums1):
            ans.extend(nums2[j:])
            return
        if j == len(nums2):
            ans.extend(nums1[i:])
            return

        if nums1[i] <= nums2[j]:
            ans.append(nums1[i])
            dfs(i + 1, j)
        else:
            ans.append(nums2[j])
            dfs(i, j + 1)

    dfs(0, 0)
    return ans

LC21 - 合并两个有序链表#

非常经典了。

Python3 点击展开代码

20 lines 展开代码

class ListNode:
    def __init__(self,val = 0, next = None):
        self.val = val
        self.next = next
    
def solution(list1:ListNode,list2:ListNode)->ListNode:
    dummy = ListNode()
    p = dummy
    while list1 and list2:
        if list1.val <= list2.val:
            p.next = ListNode(list1.val)
            p = p.next
            list1 = list1.next
        else:
            p.next = ListNode(list2.val)
            p = p.next
            list2 = list2.next            

    p.next = list1 if list1 else list2
    return dummy.next

LC392 - 判断子序列#

这题也是一边一个指针，按照规则推进的题目，严格来说不是归并题，不过也放在这里了。

Python3 点击展开代码

8 lines 展开代码

def solution(s:str,t:str)->bool:
    p, q = 0, 0
    # 如果p能走到最后，说明是成立的
    while p<len(s) and q<len(t):
        if s[p] == t[q]:
            p+=1
        q+=1
    return p == len(s)

LC986 - 区间列表的交集#

这一题，把单元素换成了一个区间，我们注意相交规则和移动规则。一般，我们移动右边界较小的一侧，因为这样还可能构成更多相交。

Python3 点击展开代码

18 lines 展开代码

def intervalIntersection(self, firstList: list[list[int]], secondList: list[list[int]]) -> list[list[int]]:
    p, q = 0, 0
    ans = []

    while p < len(firstList) and q < len(secondList):
        # 交集题常用
        start = max(firstList[p][0], secondList[q][0])
        end = min(firstList[p][1], secondList[q][1])

        if start <= end:
            ans.append([start, end])

        if firstList[p][1] <= secondList[q][1]:
            p += 1
        else:
            q += 1

    return ans

JZ52 - 两个链表的第一个公共节点#

这题头一次想很晕，实际是公式打法，公共路程法：

Python3 点击展开代码

11 lines 展开代码

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
    p,q = headA,headB
    while p != q:
        p = p.next if p else headB
        q = q.next if q else headA
    return p

固定点 + 双指针#

固定点双指针题，一般是要在变化的范围内不断用双指针解。

LC15 - 三数之和#

这一题注意为了防止重复，确定答案后移动指针要确认不是相同的值，由于排序了所以相同的值在同一段：

Python3 点击展开代码

23 lines 展开代码

def threeSum(self, nums: list[int]) -> list[list[int]]:
    nums.sort()
    ans = []
    for i in range(len(nums)-2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        left, right = i + 1, len(nums) - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            # 以0为分界决定移动哪个指针
            if s < 0:
                left += 1
            elif s > 0:
                right -= 1
            else:
                ans.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
    return ans

LC16 - 最接近的三数之和#

与三数之和的区别只在于找到答案的判定，由于本题只要返回最近和甚至不用去重。

Python3 点击展开代码

20 lines 展开代码

def threeSumClosest(self, nums: list[int], target: int) -> int:
    min_diff = float('inf')
    ans = 0
    nums.sort()
    for i in range(len(nums)-2):
        j = i + 1
        k = len(nums) - 1
        while j<k:
            total = nums[i] + nums[j] + nums[k]
            diff = abs(target-total)
            if diff < min_diff:
                min_diff = diff
                ans = total
            if total < target:
                j+=1
            elif total > target:
                k-=1 
            else:
                return total
    return ans

LC18 - 四数之和#

四数之和实际上就是固定两个位置之后再使用双指针即可，跳过的思路几乎和三数之和一样：

Python3 点击展开代码

25 lines 展开代码

def fourSum(self, nums: list[int], target: int) -> list[list[int]]:
    ans = []
    nums.sort()
    for i in range(len(nums)):
        if i>0 and nums[i] == nums[i-1]:
            continue
        for j in range(i+1,len(nums)):
            if j>i+1 and nums[j] == nums[j-1]:
                continue
            p = j + 1
            q = len(nums)-1
            while p<q:
                if nums[i]+nums[j]+nums[p]+nums[q] == target:
                    ans.append([nums[i],nums[j],nums[p],nums[q]])
                    p+=1
                    q-=1
                    while p<q and nums[p] == nums[p-1]:
                        p+=1
                    while p<q and nums[q] == nums[q+1]:
                        q-=1
                elif nums[i]+nums[j]+nums[p]+nums[q] < target:
                    p+=1
                else:
                    q-=1
    return ans

拓展 - N数之和#

做一点小扩展，已经解决了两数、三数、四数之和，那么N数之和是不是要固定N-1个数字呢。其实，我们可以通过每次固定一个点，让问题降级，从而跌落到我们熟悉的问题上。

Python3 点击展开代码

36 lines 展开代码

# n数之和，start代表从哪个索引开始计算，这是为了方便递归的设计
def NSum(self, nums: list[int], n:int, start:int, target: int) -> list[list[int]]:
    sz = len(nums)
    res = []
    if n<2 or sz<n:
        return res
    # 2Sum问题
    if n == 2:
        lo, hi = start, sz - 1
        while lo<hi:
            total = nums[lo] + nums[hi]
            left, right = nums[lo], nums[hi]
            if total == target:
                res.append([left,right])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == left:
                    lo += 1
                while lo < hi and nums[hi] == right:
                    hi -= 1
            elif total>target:
                hi -= 1
            else:
                lo += 1
        return res
    # 否则，开始递归
    else:
        for i in range(start,sz):
            if i>start and nums[i] == nums[i-1]:
                continue
            subs = self.NSum(nums,n-1,i+1,target-nums[i])
            # (n-1)Sum问题加上nums[i]就是nSum
            for sub in subs:
                sub.append(nums[i])
                res.append(sub)
        return res

LC611 - 有效三角形的个数#

这一题可以转化为最小的两个数字的和是否大于第三个数，从而用三数之和变体做，固定最大的数，用双指针看前面的数：

Python3 点击展开代码

15 lines 展开代码

def triangleNumber(self, nums: list[int]) -> int:
    nums.sort()
    count = 0
    for k in range(len(nums) - 1, 1, -1):
        i = 0
        j = k - 1
        while i < j:
            if nums[i] + nums[j] > nums[k]:
                # 此时中间的数字全部满足要求
                count += j - i
                j -= 1
            else:
                i += 1

    return count

链表双指针技巧#

LC160 - 相交链表#

与两个链表的第一个公共节点一样，不用看了。

LC234 - 回文链表#

回文链表是链表指针操作的好题，综合了找中点和翻转：

Python3 点击展开代码

26 lines 展开代码

class ListNode:
    def __init__(self,val = 0,next = None):
        self.val = val
        self.next = next

def solution(self,head:ListNode)->bool:
    if not head:
        return True
    # 先找中点，偶数要中前
    fast,slow = head, head
    while fast.next and fast.next.next:
        fast = fast.next.next
        slow = slow.next
    # 翻转
    curr = slow.next
    prev = None
    while curr:
        curr.next, prev, curr = prev,curr, curr.next
    
    # 比较
    while prev:
        if prev.val != head.val:
            return False
        prev = prev.next
        head = head.next
    return True

LC143 - 重排链表#

这一题就是从中间断开，后面翻转，然后合并。本题需要注意的最大问题是，要求原地合并保留原本的head，这样穿针引线可能会绕一点，也要注意保留下一个元素防止丢失。不过，还是推荐直接用如下方法"Z型合并"：

Python3 点击展开代码

40 lines 展开代码

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def solution(self, head: ListNode) -> None:
    if not head or not head.next:
        return

    # 1. 找中点
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

    # 2. 反转后半段
    second = slow.next
    slow.next = None

    prev = None
    curr = second
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt

    # 3. 交替合并前半段和反转后的后半段
    first = head
    second = prev

    while second:
        tmp1 = first.next
        tmp2 = second.next

        first.next = second
        second.next = tmp1

        first = tmp1
        second = tmp2

LC24 - 两两交换链表中的节点#

本题也是经典题，两种解法，保留下一个节点的循环交换，或者干脆递归。递归的解法比较简洁好想，所以下面直接递归。

Python3 点击展开代码

14 lines 展开代码

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def swapPairs(self, head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    curr = head
    prev = None
    for _ in range(2):
        curr.next, prev, curr = prev,curr, curr.next
    head.next = swapPairs(curr)
    return prev

LC25 - K个一组翻转链表#

如果采用递归的策略，跟上一题基本就没区别了，注意退出条件是小于K个剩余节点。

Python3 点击展开代码

19 lines 展开代码

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseKGroup(self, head: ListNode,k:int) -> ListNode:
    # 如果剩余少于k个直接退出
    p = head
    for _ in range(k):
        if not p:
            return head
        p = p.next

    curr = head
    prev = None
    for _ in range(k):
        curr.next, prev, curr = prev,curr, curr.next
    head.next = reverseKGroup(curr,k)
    return prev

双指针问题总结#

好了，我们刷了这么多双指针题目，可以做一个总结了。相向、同向、快慢、归并、读写、固定点、链表技巧…… 简单梳理一下，该在哪些情况下想到这些解法呢？

双指针不是一种具体代码，而是一类"用两个位置压缩搜索空间"的思想。它的核心不是一定要有两个变量，而是：我们能不能用两个指针维护某种状态，并且每次移动其中一个指针时，都能确定不会错过答案。

所以判断一道题能不能用双指针，可以先问自己三个问题：

题目是不是在处理数组、字符串、链表、区间这类线性结构？
指针移动后，能不能排除一批不可能的情况？
是否存在某种单调性、顺序性、窗口性质、链表距离关系？

如果答案是肯定的，就可以优先往双指针方向想。

1. 相向双指针：两端向中间收缩#

相向双指针最典型的形态是：

Python3 点击展开代码

8 lines 展开代码

left, right = 0, len(nums) - 1
while left < right:
    if 条件满足:
        处理答案
    elif 需要变大:
        left += 1
    else:
        right -= 1

这一类题的关键词是：有序、两端、回文、最大面积、两数之和。

典型题目：

LC167 两数之和II
LC11 盛最多水的容器
LC125 验证回文串
LC680 验证回文串II
LC881 救生艇

相向双指针的本质是"每次移动一边，都能排除一批情况"。比如有序数组两数之和中，如果当前和太小，移动右指针只会更小或者不变，没意义，所以只能移动左指针让和变大。

这类题最重要的是想清楚：为什么移动这个指针不会错过答案？

2. 同向双指针：滑动窗口#

同向双指针一般就是滑动窗口：

Python3 点击展开代码

12 lines 展开代码

left, right = 0, 0
while right < len(nums):
    # 右边界进窗口
    window_add(nums[right])
    right += 1

    while 窗口不满足条件:
        # 左边界出窗口
        window_remove(nums[left])
        left += 1

    更新答案

这一类题的关键词是：连续子数组、连续子串、最长、最短、包含、至多、恰好。

典型题目：

LC3 无重复字符的最长子串
LC209 长度最小的子数组
LC76 最小覆盖子串
LC438 找到字符串中所有字母异位词
LC567 字符串的排列
LC904 水果成篮
LC1004 最大连续1的个数III
LC713 乘积小于K的子数组

滑动窗口的本质是"维护一个连续区间的状态"。右指针负责扩大窗口，左指针负责在条件不满足时收缩窗口。

这里最容易错的是收缩条件：

求最长：通常在窗口不合法时收缩，合法后更新最大值。
求最短：通常在窗口合法时不断收缩，并在收缩前更新最小值。
固定长度：窗口长度超过目标长度就收缩。

3. 快慢指针：速度差、距离差、判环、中点#

快慢指针常见于链表，但不只适用于链表。只要一个状态能不断跳到下一个状态，就可能用快慢指针。

常见模板一，判环：

Python3 点击展开代码

7 lines 展开代码

slow, fast = head, head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        return True
return False

常见模板二，找环入口：

Python3 点击展开代码

15 lines 展开代码

slow, fast = head, head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        break

if not fast or not fast.next:
    return None

p = head
while p != slow:
    p = p.next
    slow = slow.next
return p

常见模板三，找中点：

Python3 点击展开代码

5 lines 展开代码

slow, fast = head, head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
return slow

典型题目：

LC141 环形链表
LC142 环形链表II
LC876 链表的中间结点
LC19 删除链表的倒数第N个结点
LC202 快乐数
LC287 寻找重复数

快慢指针的本质是"制造速度差或距离差"。环形链表中，快指针每次多走一步，所以如果有环一定会追上慢指针；删除倒数第N个节点中，先让快指针领先N步，本质是在维护固定距离。

注意，快乐数和寻找重复数虽然看起来不像链表，但都可以抽象成：

Python3 代码示例

1 lines

状态 x -> 下一个状态 next(x)

只要不断跳转会进入环，就能用 Floyd 快慢指针。

4. 读写双指针：一个读，一个写#

读写双指针的模板一般是：

Python3 点击展开代码

6 lines 展开代码

write = 0
for read in range(len(nums)):
    if nums[read] 应该保留:
        nums[write] = nums[read]
        write += 1
return write

这一类题的关键词是：原地删除、原地保留、移动元素、压缩数组。

典型题目：

LC26 删除有序数组中的重复项
LC27 移除元素
LC80 删除有序数组中的重复项II
LC283 移动零
LC75 颜色分类

读写双指针的本质是"读指针扫描旧数组，写指针维护新数组的下一个位置"。它通常适用于可以覆盖旧值的题目。

但是要注意，覆盖不是万能的。移动零可以覆盖，因为所有非零元素先写到前面，后面统一补零，不会丢失信息。颜色分类不能简单覆盖，因为 0、1、2 都是有效信息，直接写前后会把还没处理的元素覆盖掉，所以要用交换，也就是荷兰国旗三路划分。

读写双指针最常见的坑是：

read 每轮都要移动，不要在 if 里面加一次、外面又加一次。
覆盖前要判断这个题能不能丢弃被覆盖的旧值。
有序数组去重可以利用相邻关系，无序数组去重一般不能直接这样做。

5. 归并型双指针：两个序列一起走#

归并型双指针通常是一边一个指针：

Python3 点击展开代码

12 lines 展开代码

i, j = 0, 0
ans = []
while i < len(a) and j < len(b):
    if a[i] 更应该被处理:
        ans.append(a[i])
        i += 1
    else:
        ans.append(b[j])
        j += 1

ans.extend(a[i:])
ans.extend(b[j:])

这一类题的关键词是：两个有序数组、两个链表、两个区间列表、两个字符串匹配。

典型题目：

LC88 合并两个有序数组
LC21 合并两个有序链表
LC392 判断子序列
LC986 区间列表的交集
JZ52 两个链表的第一个公共节点

归并型双指针的本质是"两边各维护一个当前位置，每次根据规则推进一边或两边"。合并有序数组、合并链表是最标准的归并；判断子序列更准确地说是匹配型双指针，但它也是两个序列一起推进。

这里要特别记住 LC88：

如果目标数组后面有空位，优先从后往前填。
如果没有空位，通常新建数组从前往后合并。

从后往前的原因是：从前往后会覆盖 nums1 里还没处理的有效元素，而从后往前正好利用尾部空位。

6. 固定点 + 双指针：降维处理#

固定点 + 双指针，一般用于 N数之和 或类似计数问题：

Python3 点击展开代码

15 lines 展开代码

nums.sort()
for i in range(len(nums)):
    if i > 0 and nums[i] == nums[i - 1]:
        continue
    left, right = i + 1, len(nums) - 1
    while left < right:
        total = nums[i] + nums[left] + nums[right]
        if total < target:
            left += 1
        elif total > target:
            right -= 1
        else:
            记录答案
            left += 1
            right -= 1

这一类题的关键词是：三数之和、四数之和、N数之和、固定一个数、排序后查找。

典型题目：

LC15 三数之和
LC16 最接近的三数之和
LC18 四数之和
LC611 有效三角形的个数

固定点 + 双指针的本质是"固定一部分变量，把高维问题降成两数问题"。三数之和就是固定一个数，然后在右侧区间里做两数之和；四数之和就是固定两个数，再在剩余区间里做两数之和。

这一类题最容易错的是去重：

固定点要去重。
找到答案后，左右指针也要跳过重复值。
最接近的三数之和不需要去重，因为只返回一个和，不返回所有组合。

有效三角形个数虽然看起来不是求和等于某个值，但它也是固定最大边，然后在左侧用双指针批量计数。它的关键是单调性：如果 nums[i] + nums[j] > nums[k]，那么从 i 到 j - 1 的左边界都能和 j, k 组成三角形，所以可以一次加 j - i。

7. 链表双指针：先断、再反、再接#

链表题里的双指针不只是移动速度，还经常和"断链、反转、合并"组合出现。

典型题目：

LC160 相交链表
LC234 回文链表
LC143 重排链表
LC24 两两交换链表中的节点
LC25 K个一组翻转链表

链表题有几个固定意识：

可能操作头节点时，用 dummy。
改 next 之前，先保存后续节点。
切链表时，记得断开，比如 slow.next = None。
反转链表的核心永远是 curr.next, prev, curr = prev, curr, curr.next，但面试里为了可读性，也可以拆成 nxt 三步写。
合并两个旧链表时，不要新建值节点，通常是移动旧节点。

比如重排链表，整体流程就是：

1
找中点 -> 断开 -> 反转后半段 -> 交替合并

链表题的难点往往不是算法本身，而是指针改动顺序。只要涉及 next 重连，就先把后面要用的节点存起来。

8. 题型判断表#

最后给一个简单判断表，方便刷题时快速定位：

题目特征	优先想到
有序数组，两端比较	相向双指针
回文、反转字符串	相向双指针
连续子数组/子串，最长/最短/包含	滑动窗口
原地删除、原地保留、移动元素	读写双指针
链表判环、找中点、倒数第N个	快慢指针
状态不断跳转并可能成环	Floyd快慢指针
合并两个有序结构	归并型双指针
两个字符串按顺序匹配	匹配型双指针
三数、四数、N数之和	固定点 + 双指针
链表重排、回文链表	快慢指针 + 反转 + 合并

9. 最后记忆#

双指针题的关键不是背代码，而是抓住"指针含义"和"不漏答案的移动理由"。

每次写双指针，可以先在草稿里写清楚：

1
left / right / slow / fast / read / write 分别代表什么？
2
哪个区间已经处理完？
3
哪个区间还未知？
4
什么时候移动左指针？
5
什么时候移动右指针？
6
移动后会不会漏掉答案？

如果这几个问题都能回答出来，代码就基本不会乱。

我的个人记忆方式是：

1
两端排除：相向
2
连续区间：滑窗
3
一读一写：读写
4
速度距离：快慢
5
两个序列：归并
6
固定降维：N数之和
7
链表重连：先存 next，再改 next

介绍#

相向双指针#

LC167 - 两数之和II#

LC11 - 盛最多水的容器#

LC125 - 验证回文串#

LC680 - 验证回文串II#

LC344 - 反转字符串#

LC881 - 救生艇#

同向双指针#

LC3 - 无重复字符的最长子串#

LC209 - 长度最小的子数组#

LC76 - 最小覆盖子串#

LC438 - 找到字符串中所有字母异位词#

LC567 - 字符串的排列#

LC904 - 水果成篮#

LC1004 - 最大连续1的个数III#

LC713 - 乘积小于K的子数组#

快慢指针#

LC141 - 环形链表#

LC142 - 环形链表II#

LC876 - 链表的中间结点#

LC19 - 删除链表的倒数第N个结点#

LC202 - 快乐数#

LC287 - 寻找重复数#

读写双指针#

LC26 - 删除有序数组中的重复项#

LC27 - 移除元素#

LC80 - 删除有序数组中的重复项II#

LC283 - 移动零#

LC75 - 颜色分类#

归并型双指针#

LC88 - 合并两个有序数组#

LC21 - 合并两个有序链表#

LC392 - 判断子序列#

LC986 - 区间列表的交集#

JZ52 - 两个链表的第一个公共节点#

固定点 + 双指针#

LC15 - 三数之和#

LC16 - 最接近的三数之和#

LC18 - 四数之和#

拓展 - N数之和#

LC611 - 有效三角形的个数#

链表双指针技巧#

LC160 - 相交链表#

LC234 - 回文链表#

LC143 - 重排链表#

LC24 - 两两交换链表中的节点#

LC25 - K个一组翻转链表#

双指针问题总结#

1. 相向双指针：两端向中间收缩#

2. 同向双指针：滑动窗口#

3. 快慢指针：速度差、距离差、判环、中点#

4. 读写双指针：一个读，一个写#

5. 归并型双指针：两个序列一起走#

6. 固定点 + 双指针：降维处理#

7. 链表双指针：先断、再反、再接#

8. 题型判断表#

9. 最后记忆#

算法

留言

文章目录