LeetCode Patterns ·

🎯 Two Pointers

1️⃣ Core Framework

When discussing Two Pointers, I frame it as:

What problem pattern it solves
Why two pointers reduce complexity
Opposite-direction pointers
Same-direction pointers
Fast and slow pointers
Sliding window relationship
Common interview problems
Edge cases and trade-offs
How to explain it like a senior engineer

2️⃣ What Problem Are We Solving?

Two pointers is a technique for scanning a collection using two indexes or references.

It is commonly used when we need to:

Search pairs
Remove duplicates
Reverse data
Partition arrays
Detect cycles
Find subarrays
Optimize brute-force nested loops

The main idea is:

Instead of checking every pair with O(n²),
use two moving pointers to scan the data in O(n).

👉 Interview Answer

Two pointers is an optimization technique where we use two indexes or references to scan data more efficiently.

It is useful when the problem has ordering, symmetry, or a window-like structure.

Instead of using nested loops, we move the pointers based on problem-specific rules and often reduce the time complexity from O(n²) to O(n).

3️⃣ Why Two Pointers Work

Brute Force Problem

Many array problems start with this pattern:

for i in range(n):
    for j in range(i + 1, n):
        check pair

This is usually:

O(n²)

Two Pointers Optimization

If the array is sorted, or if the problem has monotonic behavior, we can often do:

left = 0
right = n - 1

while left < right:
    decide whether to move left or right

This becomes:

O(n)

Key Requirement

Two pointers usually works when moving a pointer gives us useful information.

For example:

If sum is too small, move left to increase the sum.
If sum is too large, move right to decrease the sum.

👉 Interview Answer

Two pointers works when the search space can be reduced safely.

In sorted arrays, moving the left pointer usually increases the value, and moving the right pointer usually decreases the value.

Because each pointer only moves in one direction, every element is visited at most once, so the algorithm becomes linear.

4️⃣ Main Two Pointer Patterns

Pattern 1: Opposite Direction

left →                ← right

Used for:

Two Sum sorted
Valid palindrome
Container with most water
Reverse array
3Sum after sorting

Pattern 2: Same Direction

slow →
fast →

Used for:

Remove duplicates
Move zeros
Partition array
Compress array
In-place overwrite

Pattern 3: Fast and Slow Pointer

slow moves 1 step
fast moves 2 steps

Used for:

Linked list cycle detection
Find middle of linked list
Detect duplicate number
Cycle entrance

Pattern 4: Sliding Window

left → window → right

Used for:

Longest substring
Minimum window substring
Subarray sum
At most K distinct characters

👉 Interview Answer

I usually classify two pointer problems into four patterns:

opposite-direction pointers, same-direction pointers, fast-slow pointers, and sliding-window pointers.

The key is to identify what each pointer represents and what condition causes each pointer to move.

5️⃣ Opposite Direction Pointers

Core Idea

Start from both ends:

left = 0
right = len(nums) - 1

while left < right:
    # check condition
    # move left or right

Example: Two Sum Sorted

Given a sorted array, find two numbers that add up to target.

def two_sum_sorted(nums, target):
    left = 0
    right = len(nums) - 1

    while left < right:
        total = nums[left] + nums[right]

        if total == target:
            return [left, right]
        elif total < target:
            left += 1
        else:
            right -= 1

    return [-1, -1]

Why It Works

Because the array is sorted:

If sum is too small, move left rightward.
If sum is too large, move right leftward.

We never need to revisit old pairs.

👉 Interview Answer

For a sorted two-sum problem, I use opposite-direction pointers.

If the current sum is smaller than target, I move the left pointer to increase the sum.

If the current sum is larger than target, I move the right pointer to decrease the sum.

Since each pointer moves at most n times, the time complexity is O(n).

6️⃣ Valid Palindrome

Problem

Check whether a string is a palindrome.

racecar → true
hello   → false

Code

def is_palindrome(s):
    left = 0
    right = len(s) - 1

    while left < right:
        if s[left] != s[right]:
            return False

        left += 1
        right -= 1

    return True

With Non-Alphanumeric Characters

def is_palindrome_clean(s):
    left = 0
    right = len(s) - 1

    while left < right:
        while left < right and not s[left].isalnum():
            left += 1

        while left < right and not s[right].isalnum():
            right -= 1

        if s[left].lower() != s[right].lower():
            return False

        left += 1
        right -= 1

    return True

👉 Interview Answer

Palindrome checking is a classic opposite-direction pointer problem.

We compare characters from both ends.

If they match, both pointers move inward.

If they differ, the string is not a palindrome.

7️⃣ Same Direction Pointers

Core Idea

Both pointers move from left to right.

Usually:

fast pointer scans the array
slow pointer tracks where to write or keep valid values

Template

slow = 0

for fast in range(len(nums)):
    if should_keep(nums[fast]):
        nums[slow] = nums[fast]
        slow += 1

Common Use Cases

Remove duplicates
Move zeros
Remove element
In-place filtering
Compact array

👉 Interview Answer

Same-direction two pointers are useful for in-place modification.

The fast pointer scans every element.

The slow pointer tracks the position where the next valid element should be written.

This avoids creating an extra array.

8️⃣ Remove Duplicates from Sorted Array

Problem

Given a sorted array, remove duplicates in-place.

[1, 1, 2, 2, 3]
→ [1, 2, 3]

Code

def remove_duplicates(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

Meaning of Pointers

fast: scans every element
slow: next write position for unique value

👉 Interview Answer

Since the array is sorted, duplicates are adjacent.

I use fast to scan the array and slow to track the next position for a unique value.

Whenever nums[fast] differs from the previous value, I write it to nums[slow] and advance slow.

9️⃣ Move Zeros

Problem

Move all zeros to the end while keeping the relative order of non-zero elements.

[0, 1, 0, 3, 12]
→ [1, 3, 12, 0, 0]

Code

def move_zeroes(nums):
    slow = 0

    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1

Why It Works

Before slow: all non-zero values are already placed.
From slow to fast: unknown or zeros.
After fast: not processed yet.

👉 Interview Answer

I use slow to track where the next non-zero value should go.

Fast scans the array.

When fast finds a non-zero value, I swap it with nums[slow].

This keeps non-zero elements in order and moves zeros to the end.

🔟 Fast and Slow Pointers

Core Idea

Fast and slow pointers are commonly used on linked lists.

slow moves 1 step
fast moves 2 steps

This can detect structural properties such as:

Cycle existence
Middle node
Cycle entry point

Why It Works for Cycle Detection

If there is a cycle:

fast pointer eventually catches slow pointer

If there is no cycle:

fast pointer reaches null

👉 Interview Answer

Fast and slow pointers are useful when the data structure is linked or cyclic.

If fast moves two steps and slow moves one step, then in a cycle, fast will eventually meet slow.

If there is no cycle, fast reaches the end.

1️⃣1️⃣ Linked List Cycle

Code

def has_cycle(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True

    return False

Complexity

Time: O(n)
Space: O(1)

👉 Interview Answer

To detect a linked list cycle, I use Floyd’s cycle detection algorithm.

Slow moves one step at a time.

Fast moves two steps at a time.

If there is a cycle, they eventually meet.

If fast reaches null, there is no cycle.

1️⃣2️⃣ Find Middle of Linked List

Code

def middle_node(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

Explanation

When fast reaches the end:

slow is at the middle

👉 Interview Answer

To find the middle of a linked list, I use fast and slow pointers.

Fast moves two steps while slow moves one step.

When fast reaches the end, slow is at the middle.

1️⃣3️⃣ Sliding Window as Two Pointers

Relationship

Sliding window is a special form of two pointers.

left pointer controls window start
right pointer expands window end

Template

def sliding_window(nums):
    left = 0
    window_state = {}

    for right in range(len(nums)):
        # add nums[right] to window

        while window_is_invalid():
            # remove nums[left] from window
            left += 1

        # update answer

Common Problems

Longest substring without repeating characters
Minimum size subarray sum
Longest subarray with at most K distinct values
Minimum window substring

👉 Interview Answer

Sliding window is a two-pointer pattern where the right pointer expands the window and the left pointer shrinks it.

It works when we can maintain a valid window condition incrementally.

This is commonly used for substring and subarray optimization problems.

1️⃣4️⃣ Longest Substring Without Repeating Characters

Problem

Find the length of the longest substring without repeating characters.

abcabcbb → 3

Code

def length_of_longest_substring(s):
    seen = set()
    left = 0
    best = 0

    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1

        seen.add(s[right])
        best = max(best, right - left + 1)

    return best

Why It Works

The window always maintains:

no duplicate characters

When a duplicate appears, move left until the window becomes valid again.

👉 Interview Answer

I maintain a window with no duplicate characters.

The right pointer expands the window.

If the new character already exists, I move the left pointer until the duplicate is removed.

Then I update the maximum window length.

1️⃣5️⃣ Container With Most Water

Problem

Given heights, find the max area between two lines.

area = min(height[left], height[right]) * width

Code

def max_area(height):
    left = 0
    right = len(height) - 1
    best = 0

    while left < right:
        width = right - left
        area = min(height[left], height[right]) * width
        best = max(best, area)

        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return best

Key Insight

Move the shorter side.

Why?

The area is limited by the shorter height.
Moving the taller side cannot help if the shorter side stays the same.

👉 Interview Answer

For container with most water, I start with the widest possible container.

At each step, the area is limited by the shorter line.

So I move the pointer at the shorter line, hoping to find a taller boundary.

This gives an O(n) solution.

1️⃣6️⃣ Three Sum

Problem

Find all unique triplets that sum to zero.

Pattern

Sort first.
Fix one number.
Use two pointers to find the other two.

Code

def three_sum(nums):
    nums.sort()
    result = []

    for i in range(len(nums)):
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left = i + 1
        right = len(nums) - 1

        while left < right:
            total = nums[i] + nums[left] + nums[right]

            if total == 0:
                result.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

            elif total < 0:
                left += 1
            else:
                right -= 1

    return result

Complexity

Sorting: O(n log n)
Two-pointer scan for each i: O(n²)
Total: O(n²)

👉 Interview Answer

For 3Sum, I first sort the array.

Then I fix one number and use two pointers to find the remaining pair.

Sorting allows me to move pointers based on whether the current sum is too small or too large.

I also skip duplicates to avoid returning repeated triplets.

1️⃣7️⃣ How to Decide Which Pointer to Move

Opposite Direction

Usually based on comparison:

sum < target → move left
sum > target → move right

Same Direction

Usually based on validity:

valid element → write to slow
invalid element → skip

Sliding Window

Usually based on window condition:

window valid → expand right
window invalid → shrink left

Fast and Slow

Usually based on speed difference:

fast moves faster to detect cycle or locate middle

👉 Interview Answer

The most important part of two pointers is defining the movement rule.

I ask:

What does each pointer represent?

What invariant must remain true?

Which pointer movement safely reduces the search space?

Once the invariant is clear, the implementation becomes straightforward.

1️⃣8️⃣ Common Edge Cases

Empty Input

[]
""
None linked list

One Element

[1]
"a"
single-node linked list

Duplicates

[1, 1, 1, 1]

Boundary Conditions

left < right
left <= right
fast and fast.next

Sorted vs Unsorted

Two pointers often requires sorted data.

If input is unsorted, ask:

Can I sort it?
Will sorting break index requirements?
Do I need original positions?

👉 Interview Answer

The main edge cases are empty input, single element input, duplicates, and pointer boundary conditions.

I also check whether sorting is allowed, because many two-pointer solutions depend on sorted order.

If original indexes are required, sorting may require storing the original indexes.

1️⃣9️⃣ Complexity Analysis

Time Complexity

Most two-pointer scans are:

O(n)

Because each pointer moves at most n times.

Some problems require sorting first:

O(n log n)

Some problems combine a fixed loop with two pointers:

3Sum → O(n²)

Space Complexity

Usually:

O(1)

Unless we need:

Hash set
Hash map
Result list
Sorting extra space depending on language

👉 Interview Answer

Two pointers often gives O(n) time because each pointer moves monotonically and never moves backward.

Space is usually O(1), especially for in-place array problems.

If sorting is required, we should include O(n log n) time and discuss whether sorting changes the problem requirements.

2️⃣0️⃣ Two Pointers vs Hash Map

Two Pointers

Best when:

Input is sorted
We can sort input
Need O(1) extra space
Need pair or window structure

Hash Map

Best when:

Input is unsorted
Need direct lookup
Need original indexes
Sorting would break requirements

Example: Two Sum

Approach	Time	Space	Requirement
Hash Map	O(n)	O(n)	Works on unsorted array
Two Pointers	O(n)	O(1)	Requires sorted array
Sort + Two Pointers	O(n log n)	O(1) or O(n)	May lose original index

👉 Interview Answer

For two-sum style problems, I choose between hash map and two pointers based on input constraints.

If the array is unsorted and I need original indexes, hash map is usually better.

If the array is sorted or sorting is allowed and I want constant extra space, two pointers is a strong option.

2️⃣1️⃣ Senior-Level Thinking

What a Senior Engineer Should Explain

Do not only say:

Use two pointers.

Explain:

Why the brute force is inefficient
What property allows pointer movement
What invariant is maintained
Why no valid answer is skipped
Complexity and trade-offs

Example Explanation

Because the array is sorted,
moving left increases the sum,
and moving right decreases the sum.

So when the sum is too small,
any pair using the current left and smaller right cannot work.
Therefore we can safely move left.

👉 Interview Answer

At senior level, I would not just describe the code.

I would explain the invariant and why each pointer movement is safe.

The key is proving that we are reducing the search space without skipping a valid answer.

2️⃣2️⃣ Common Mistakes

Mistake 1: Moving the Wrong Pointer

sum too small but moving right

Mistake 2: Incorrect Loop Condition

while left <= right:

Sometimes it should be:

while left < right:

Mistake 3: Forgetting Duplicates

Common in:

3Sum
4Sum
Remove duplicates
Sorted pair problems

Mistake 4: Infinite Loop

Forgetting to move pointers after finding an answer.

Mistake 5: Sorting When Indexes Matter

Sorting may destroy original index positions.

👉 Interview Answer

The most common bugs are wrong pointer movement, incorrect loop boundaries, duplicate handling, and forgetting that sorting may break original index requirements.

I always define the invariant first, then implement pointer movement carefully.

2️⃣3️⃣ Standard Templates

Opposite Direction Template

left = 0
right = len(nums) - 1

while left < right:
    if condition_met:
        # update answer
        left += 1
        right -= 1
    elif need_larger_value:
        left += 1
    else:
        right -= 1

Same Direction Template

slow = 0

for fast in range(len(nums)):
    if is_valid(nums[fast]):
        nums[slow] = nums[fast]
        slow += 1

Fast Slow Template

slow = head
fast = head

while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

    if slow == fast:
        return True

Sliding Window Template

left = 0

for right in range(len(nums)):
    add(nums[right])

    while window_invalid():
        remove(nums[left])
        left += 1

    update_answer()

🧠 Staff-Level Answer Final

👉 Interview Answer Full Version

Two pointers is an algorithmic technique where we use two indexes or references to scan a data structure efficiently.

It is commonly used for arrays, strings, and linked lists.

The main value is that it can reduce brute-force O(n²) pair checking into O(n), when the problem has sorted order, monotonic behavior, symmetry, or a maintainable window condition.

There are several common patterns.

Opposite-direction pointers start from both ends and move inward. This is useful for sorted two-sum, palindrome checking, reversing arrays, container with most water, and 3Sum after sorting.

Same-direction pointers move from left to right. Usually the fast pointer scans the input and the slow pointer tracks the next write position. This is useful for removing duplicates, moving zeros, and in-place filtering.

Fast and slow pointers are commonly used for linked lists. The fast pointer moves faster than the slow pointer, which helps detect cycles or find the middle node.

Sliding window is also a two-pointer pattern. The right pointer expands the window, and the left pointer shrinks the window when the window becomes invalid.

At a senior level, the key is not just knowing the template. The important part is explaining the invariant.

I would define what each pointer represents, what condition controls pointer movement, and why moving a pointer does not skip any valid answer.

For example, in a sorted two-sum problem, if the current sum is too small, moving the right pointer left would only make the sum smaller, so the only useful move is to move the left pointer right.

Since each pointer moves monotonically and visits each element at most once, most two-pointer algorithms run in O(n) time and O(1) extra space.

The main trade-offs are that some problems require sorted input, sorting may change original indexes, and duplicate handling must be implemented carefully.

⭐ Final Insight

Two Pointers 的核心不是“放两个 index”，而是找到一个可以安全缩小搜索空间的规则。

Senior-level 的重点是： pointer movement 为什么正确， invariant 是什么，为什么不会跳过答案。

能讲清楚这三个点， Two Pointers 就不只是刷题技巧，而是一个清晰的 algorithmic reasoning pattern。

中文部分

🎯 Two Pointers

1️⃣ 核心框架

讨论 Two Pointers 时，我通常从：

它解决什么问题
为什么可以降低复杂度
相向双指针
同向双指针
快慢指针
Sliding window 的关系
高频面试题
Edge cases 和 trade-offs
高级工程师应该怎么解释

2️⃣ 要解决什么问题？

Two Pointers 是一种用两个 index 或 reference 扫描数据的技巧。

它常用于：

Search pairs
Remove duplicates
Reverse data
Partition arrays
Detect cycles
Find subarrays
Optimize nested loops

核心思想是：

不要用 O(n²) 检查所有组合，
而是用两个 pointer 按规则移动，
把复杂度降到 O(n)。

👉 面试回答

Two pointers 是一种优化扫描过程的算法技巧。

它用两个 index 或 reference 来表示当前搜索范围、窗口范围，或者读写位置。

当问题存在排序、单调性、对称性，或者窗口条件时， two pointers 可以把很多 O(n²) 的暴力枚举优化成 O(n)。

3️⃣ 为什么 Two Pointers 有效？

暴力解法

很多问题一开始是：

for i in range(n):
    for j in range(i + 1, n):
        check pair

复杂度是：

O(n²)

Two Pointers 优化

如果数组有序，或者问题有单调性，可以变成：

left = 0
right = n - 1

while left < right:
    根据条件移动 left 或 right

复杂度变成：

O(n)

关键条件

Two pointers 有效的前提是：

移动某一个 pointer 可以安全排除一部分搜索空间。

例如：

sum 太小 → 移动 left，让 sum 变大
sum 太大 → 移动 right，让 sum 变小

👉 面试回答

Two pointers 的本质是安全地缩小搜索空间。

在 sorted array 中， left 往右移动通常会让值变大， right 往左移动通常会让值变小。

所以我们可以根据当前状态决定移动哪个 pointer，并且不会跳过有效答案。

4️⃣ 主要模式

Pattern 1: 相向双指针

left →                ← right

用于：

Two Sum sorted
Valid palindrome
Container with most water
Reverse array
3Sum after sorting

Pattern 2: 同向双指针

slow →
fast →

用于：

Remove duplicates
Move zeros
Partition array
Compress array
In-place overwrite

Pattern 3: 快慢指针

slow 每次走 1 步
fast 每次走 2 步

用于：

Linked list cycle detection
Find middle of linked list
Detect duplicate number
Cycle entrance

Pattern 4: Sliding Window

left → window → right

用于：

Longest substring
Minimum window substring
Subarray sum
At most K distinct characters

👉 面试回答

我通常把 two pointers 分成四类：

相向双指针、同向双指针、快慢指针、以及 sliding window。

面试中最重要的是先判断每个 pointer 代表什么，然后确定 pointer movement rule。

5️⃣ 相向双指针

核心思想

从两端开始：

left = 0
right = len(nums) - 1

while left < right:
    # check condition
    # move left or right

Example: Two Sum Sorted

def two_sum_sorted(nums, target):
    left = 0
    right = len(nums) - 1

    while left < right:
        total = nums[left] + nums[right]

        if total == target:
            return [left, right]
        elif total < target:
            left += 1
        else:
            right -= 1

    return [-1, -1]

为什么正确？

因为数组有序：

sum 太小 → left 右移，让 sum 变大
sum 太大 → right 左移，让 sum 变小

👉 面试回答

对 sorted two-sum，我会使用相向双指针。

如果当前 sum 小于 target，说明需要更大的值，所以移动 left。

如果当前 sum 大于 target，说明需要更小的值，所以移动 right。

每个 pointer 最多移动 n 次，所以复杂度是 O(n)。

6️⃣ Valid Palindrome

代码

def is_palindrome(s):
    left = 0
    right = len(s) - 1

    while left < right:
        if s[left] != s[right]:
            return False

        left += 1
        right -= 1

    return True

跳过非字母数字字符

def is_palindrome_clean(s):
    left = 0
    right = len(s) - 1

    while left < right:
        while left < right and not s[left].isalnum():
            left += 1

        while left < right and not s[right].isalnum():
            right -= 1

        if s[left].lower() != s[right].lower():
            return False

        left += 1
        right -= 1

    return True

👉 面试回答

Palindrome 是典型的相向双指针问题。

我们从两端开始比较字符。

如果相等，就同时向中间移动。

如果不相等，就不是 palindrome。

7️⃣ 同向双指针

核心思想

两个 pointer 都从左往右走。

通常是：

fast 扫描数组
slow 记录下一个有效元素应该写入的位置

Template

slow = 0

for fast in range(len(nums)):
    if should_keep(nums[fast]):
        nums[slow] = nums[fast]
        slow += 1

👉 面试回答

同向双指针常用于 in-place 修改数组。

fast pointer 负责扫描。

slow pointer 负责记录下一个应该写入的位置。

这样可以避免额外创建数组。

8️⃣ Remove Duplicates from Sorted Array

Code

def remove_duplicates(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

Pointer 含义

fast: 扫描每个元素
slow: 下一个 unique value 应该写入的位置

👉 面试回答

因为数组是 sorted， duplicates 一定是相邻的。

我用 fast 扫描数组，用 slow 记录下一个 unique value 的写入位置。

当 nums[fast] 和前一个值不同时，就把它写入 nums[slow]。

9️⃣ Move Zeros

Code

def move_zeroes(nums):
    slow = 0

    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1

Invariant

slow 左边全部是 non-zero values
fast 之前已经处理过
fast 之后还没有处理

👉 面试回答

我用 slow 记录下一个 non-zero value 应该放的位置。

fast 扫描数组。

当 fast 找到 non-zero value 时，就和 nums[slow] 交换，然后 slow 右移。

这样可以保持 non-zero values 的相对顺序。

🔟 快慢指针

核心思想

常用于 linked list。

slow 每次走 1 步
fast 每次走 2 步

可以用来：

判断是否有环
找 linked list 中点
找 cycle entrance

👉 面试回答

快慢指针适合 linked list 或 cycle 结构。

如果有环，fast pointer 最终会追上 slow pointer。

如果没有环，fast pointer 会先到达 null。

1️⃣1️⃣ Linked List Cycle

Code

def has_cycle(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True

    return False

👉 面试回答

判断 linked list 是否有环，我会使用 Floyd cycle detection。

slow 每次走一步。

fast 每次走两步。

如果存在 cycle，它们最终会相遇。

如果 fast 到达 null，说明没有 cycle。

1️⃣2️⃣ Sliding Window 是 Two Pointers 的一种

Template

def sliding_window(nums):
    left = 0
    window_state = {}

    for right in range(len(nums)):
        # add nums[right]

        while window_is_invalid():
            # remove nums[left]
            left += 1

        # update answer

👉 面试回答

Sliding window 可以看成 two pointers 的一种特殊形式。

right pointer 负责扩展窗口。

left pointer 负责在窗口不合法时收缩窗口。

它常用于 substring 和 subarray 优化问题。

1️⃣3️⃣ Longest Substring Without Repeating Characters

Code

def length_of_longest_substring(s):
    seen = set()
    left = 0
    best = 0

    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1

        seen.add(s[right])
        best = max(best, right - left + 1)

    return best

👉 面试回答

我维护一个没有重复字符的窗口。

right pointer 扩展窗口。

如果加入的字符已经存在，就移动 left pointer，直到窗口重新合法。

每次窗口合法后更新最大长度。

1️⃣4️⃣ Container With Most Water

Code

def max_area(height):
    left = 0
    right = len(height) - 1
    best = 0

    while left < right:
        width = right - left
        area = min(height[left], height[right]) * width
        best = max(best, area)

        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return best

核心 insight

面积由较短的那一边决定。
所以移动较高的一边没有意义。
应该移动较短的一边，尝试找到更高的边界。

👉 面试回答

Container with most water 中，我从最宽的 container 开始。

当前面积由较短的边决定。

所以每次移动较短的那一边，因为只有这样才可能找到更大的面积。

整体复杂度是 O(n)。

1️⃣5️⃣ Three Sum

Pattern

先排序
固定一个数
然后用 two pointers 找剩下两个数

Code

def three_sum(nums):
    nums.sort()
    result = []

    for i in range(len(nums)):
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left = i + 1
        right = len(nums) - 1

        while left < right:
            total = nums[i] + nums[left] + nums[right]

            if total == 0:
                result.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

            elif total < 0:
                left += 1
            else:
                right -= 1

    return result

👉 面试回答

3Sum 我会先排序。

然后固定一个数，再用 two pointers 找另外两个数。

排序后可以根据 sum 太大或太小来移动 pointer。

同时需要跳过 duplicates，避免重复结果。

1️⃣6️⃣ 怎么决定移动哪个 Pointer？

相向双指针

sum < target → move left
sum > target → move right

同向双指针

valid element → write to slow
invalid element → skip

Sliding Window

window valid → expand right
window invalid → shrink left

快慢指针

fast 走得更快，用来检测 cycle 或定位 middle

👉 面试回答

Two pointers 最关键的是 movement rule。

我会先问：

每个 pointer 代表什么？

当前 invariant 是什么？

移动哪个 pointer 可以安全缩小搜索空间？

把这个想清楚，代码就很自然了。

1️⃣7️⃣ 常见 Edge Cases

Empty Input

[]
""
None linked list

One Element

[1]
"a"
single-node linked list

Duplicates

[1, 1, 1, 1]

Boundary Conditions

left < right
left <= right
fast and fast.next

Sorted vs Unsorted

Can I sort?
Will sorting break original indexes?
Do I need original positions?

👉 面试回答

Two pointers 的常见 edge cases 包括： empty input、single element、duplicates 和 pointer boundary。

另外要特别注意是否允许排序。

因为很多 two pointer 解法依赖 sorted order，但排序可能会破坏原始 index 信息。

1️⃣8️⃣ Complexity Analysis

Time Complexity

多数 two pointer scan 是：

O(n)

因为每个 pointer 都只单向移动。

Sorting Case

如果需要先排序：

O(n log n)

3Sum Case

O(n²)

因为外层固定一个数，内层 two pointers 扫描。

Space Complexity

通常是：

O(1)

但如果使用 set、map 或 result list，要额外计算。

👉 面试回答

Two pointers 通常是 O(n)，因为每个 pointer 都单向移动，不会反复回头。

Space 通常是 O(1)，尤其是 in-place array 问题。

如果需要 sorting，要额外考虑 O(n log n) 的时间成本，以及排序是否影响题目要求。

1️⃣9️⃣ Two Pointers vs Hash Map

Two Pointers 适合：

Input already sorted
可以排序
想要 O(1) extra space
问题有 pair/window 结构

Hash Map 适合：

Input unsorted
需要快速 lookup
需要保留 original indexes
不能排序

Approach	Time	Space	Requirement
Hash Map	O(n)	O(n)	Works on unsorted array
Two Pointers	O(n)	O(1)	Requires sorted array
Sort + Two Pointers	O(n log n)	O(1) or O(n)	May lose original index

👉 面试回答

对 two-sum 这类问题，我会根据输入条件选择 hash map 或 two pointers。

如果数组无序且需要原始 index， hash map 通常更合适。

如果数组已经 sorted，或者可以排序并且希望节省空间， two pointers 是很好的选择。

2️⃣0️⃣ 高级工程师如何解释

不要只说：

Use two pointers.

要解释：

Brute force 为什么慢
哪个性质允许移动 pointer
Invariant 是什么
为什么不会跳过答案
Complexity 和 trade-offs

Example

因为数组是 sorted，
left 右移会让 sum 变大，
right 左移会让 sum 变小。

所以当 sum 太小时，
当前 left 搭配任何更小的 right 都不可能成功，
因此可以安全移动 left。

👉 面试回答

高级工程师在解释 two pointers 时，重点不是背模板，而是解释 pointer movement 为什么正确。

我会说明 invariant 是什么，每次移动 pointer 如何缩小搜索空间，以及为什么不会跳过正确答案。

2️⃣1️⃣ 常见错误

Mistake 1: 移动错 Pointer

sum 太小却移动 right

Mistake 2: Loop Condition 错误

while left <= right:

有时应该是：

while left < right:

Mistake 3: 忘记处理 duplicates

常见于：

3Sum
4Sum
Remove duplicates
Sorted pair problems

Mistake 4: Infinite Loop

找到答案后忘记移动 pointer。

Mistake 5: 排序破坏原始 index

Two Sum 原题如果要求原始 index，排序就要小心。

👉 面试回答

Two pointers 常见 bug 包括： pointer 移动规则错误、 loop boundary 错误、 duplicates 没处理、以及排序破坏原始 index。

我通常会先定义 invariant，再写 pointer movement。

2️⃣2️⃣ 标准模板

相向双指针模板

left = 0
right = len(nums) - 1

while left < right:
    if condition_met:
        # update answer
        left += 1
        right -= 1
    elif need_larger_value:
        left += 1
    else:
        right -= 1

同向双指针模板

slow = 0

for fast in range(len(nums)):
    if is_valid(nums[fast]):
        nums[slow] = nums[fast]
        slow += 1

快慢指针模板

slow = head
fast = head

while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

    if slow == fast:
        return True

Sliding Window 模板

left = 0

for right in range(len(nums)):
    add(nums[right])

    while window_invalid():
        remove(nums[left])
        left += 1

    update_answer()

🧠 Staff-Level Answer Final

👉 面试回答完整版本

Two pointers 是一种用两个 index 或 reference 高效扫描数据结构的算法技巧。

它常用于 array、string 和 linked list。

核心价值是，当问题存在 sorted order、monotonic behavior、symmetry，或者可维护的 window condition 时，它可以把很多 O(n²) 的暴力枚举优化成 O(n)。

Two pointers 有几种常见模式。

第一种是相向双指针。两个 pointer 从两端向中间移动，常用于 sorted two-sum、palindrome、reverse array、container with most water，以及排序后的 3Sum。

第二种是同向双指针。 fast pointer 负责扫描， slow pointer 负责记录写入位置。这种模式常用于 remove duplicates、move zeros 和 in-place filtering。

第三种是快慢指针。 fast pointer 比 slow pointer 走得更快，常用于 linked list cycle detection 和 finding middle node。

第四种是 sliding window。 right pointer 扩展窗口， left pointer 在窗口不合法时收缩窗口。

高级工程师解释 two pointers 时，不应该只说使用模板，而应该说明 invariant 和 pointer movement rule。

我会解释每个 pointer 代表什么，当前状态是否合法，以及为什么移动某个 pointer 可以安全缩小搜索空间，不会跳过正确答案。

例如 sorted two-sum 中，如果当前 sum 太小，移动 right 只会让 sum 更小，所以只能移动 left 来寻找更大的值。

因为每个 pointer 都是单向移动，每个元素最多被访问常数次，所以大多数 two pointer 解法是 O(n) time 和 O(1) space。

主要 trade-offs 是：有些问题依赖 sorted input， sorting 可能破坏 original index， duplicates 需要小心处理， pointer boundary 也容易出错。

⭐ Final Insight

Two Pointers 的核心不是“两个 index”，而是一个可以安全缩小搜索空间的 movement rule。

高级工程师真正要讲清楚的是：

pointer 代表什么， invariant 是什么，为什么移动 pointer 不会跳过答案。

这才是 Two Pointers 的本质。