LeetCode 双指针算法总结：技巧与实战

引言

双指针是一种常用的算法技巧，在解决数组、链表、字符串等问题时非常有效。本文将深入探讨双指针算法的基本概念、常见类型、应用场景以及在 LeetCode 上的实际应用。

1. 双指针算法概述

双指针算法involves using two pointers to solve a problem, usually to search for a pair of elements or to traverse the data structure. 这种技巧可以大大提高算法的效率，通常可以将时间复杂度从 O(n^2) 降低到 O(n)。

2. 双指针的常见类型

2.1 对撞指针

两个指针分别从数组的两端向中间移动。

应用场景：

  • 有序数组的 Two Sum 问题
  • 回文串判断

示例：有序数组的 Two Sum（LeetCode 167）

1
2
3
4
5
6
7
8
9
10
11
def twoSum(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            return [left + 1, right + 1]  # 题目要求索引从1开始
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return []  # 没有找到符合条件的两个数

2.2 快慢指针

两个指针从同一端出发，但是移动速度不同。

应用场景：

  • 链表中环的检测
  • 寻找链表的中点
  • 删除链表的倒数第 N 个节点

示例：链表中环的检测（LeetCode 141）

1
2
3
4
5
6
7
8
9
10
11
def hasCycle(head):
    if not head or not head.next:
        return False
    slow = head
    fast = head.next
    while slow != fast:
        if not fast or not fast.next:
            return False
        slow = slow.next
        fast = fast.next.next
    return True

2.3 滑动窗口

一左一右两个指针构成一个窗口，滑动遍历整个数组或字符串。

应用场景：

  • 子串问题
  • 子数组问题

示例：无重复字符的最长子串（LeetCode 3）

1
2
3
4
5
6
7
8
9
10
11
def lengthOfLongestSubstring(s):
    char_index = {}
    max_length = 0
    start = 0
    for end, char in enumerate(s):
        if char in char_index and char_index[char] >= start:
            start = char_index[char] + 1
        else:
            max_length = max(max_length, end - start + 1)
        char_index[char] = end
    return max_length

3. 双指针解题技巧

3.1 合并两个有序数组

LeetCode 88: Merge Sorted Array

1
2
3
4
5
6
7
8
9
10
def merge(nums1, m, nums2, n):
    p1, p2, p = m - 1, n - 1, 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

3.2 删除排序数组中的重复项

LeetCode 26: Remove Duplicates from Sorted Array

1
2
3
4
5
6
7
8
9
def removeDuplicates(nums):
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

3.3 三数之和

LeetCode 15: 3Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def threeSum(nums):
    nums.sort()
    result = []
    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:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left+1]:
                    left += 1
                while left < right and nums[right] == nums[right-1]:
                    right -= 1
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    return result

3.4 盛最多水的容器

LeetCode 11: Container With Most Water

1
2
3
4
5
6
7
8
9
10
11
def maxArea(height):
    left, right = 0, len(height) - 1
    max_area = 0
    while left < right:
        area = min(height[left], height[right]) * (right - left)
        max_area = max(max_area, area)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_area

4. 双指针算法的优化思路

  1. 预处理: 对于某些问题，可以先对数据进行排序，这样可以使用双指针算法更高效地解决问题。

  2. 边界条件处理: 在实现双指针算法时，要特别注意边界条件的处理，确保不会发生越界错误。

  3. 去重处理: 在处理类似 3Sum、4Sum 等问题时，要注意去重，避免产生重复的结果。

  4. 快慢指针的应用: 在处理链表问题时，快慢指针可以帮助我们找到中点、检测环、删除特定节点等。

  5. 滑动窗口的灵活应用: 对于子串、子数组问题，灵活运用滑动窗口可以大大提高效率。

5. 双指针算法的局限性

虽然双指针算法在许多场景下非常高效，但也存在一些局限性：

  1. 适用范围: 双指针主要适用于数组、链表、字符串等线性数据结构，对于树、图等非线性结构，可能需要其他算法。

  2. 前提条件: 某些双指针算法（如对撞指针）可能需要数据是有序的，这可能需要额外的排序步骤。

  3. 复杂度: 虽然双指针可以将很多问题的时间复杂度优化到 O(n)，但对于某些特定问题，可能存在更优的算法。

  4. 实现复杂度: 某些双指针算法（如滑动窗口）的实现可能比暴力解法更复杂，需要仔细处理各种边界情况。

结语

双指针算法是一种强大而灵活的技巧，在解决 LeetCode 问题时经常用到。掌握双指针的各种类型和应用场景，可以帮助我们更高效地解决各种算法问题。在实际应用中，要根据具体问题的特点，选择合适的双指针策略，并注意处理好边界条件和特殊情况。通过不断练习和总结，我们可以在算法解题中越来越熟练地运用双指针技巧。