03-双指针技巧

💡 核心结论

双指针本质

  • 定义：用两个指针遍历，降低时间复杂度

  • 核心：O(n²) → O(n)

  • 类型：对撞指针、快慢指针、滑动窗口

  • 适用：有序数组、链表、字符串

  • 关键：明确每个指针的含义和移动条件

三种模式

模式

特点

适用

复杂度

对撞指针

两端向中间

有序数组、回文

O(n)

快慢指针

同向不同速

链表环、中点

O(n)

滑动窗口

维护区间

子串、子数组

O(n)

👈👉 对撞指针

两数之和II（有序数组）

def two_sum(nums, target):
    left, right = 0, len(nums) - 1
    
    while left < right:
        sum_val = nums[left] + nums[right]
        if sum_val == target:
            return [left, right]
        elif sum_val < target:
            left += 1
        else:
            right -= 1
    
    return []

三数之和

def three_sum(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:
            sum_val = nums[i] + nums[left] + nums[right]
            if sum_val == 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 sum_val < 0:
                left += 1
            else:
                right -= 1
    
    return result

🐢🐰 快慢指针

环形链表

def has_cycle(head):
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    
    return False

链表中点

def find_middle(head):
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    return slow

🪟 滑动窗口

最长无重复子串

def length_of_longest_substring(s):
    char_set = set()
    left = 0
    max_len = 0
    
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)
    
    return max_len

滑动窗口模板

def sliding_window(s):
    left = 0
    window = {}  # 维护窗口状态
    result = 0
    
    for right in range(len(s)):
        # 扩大窗口
        c = s[right]
        window[c] = window.get(c, 0) + 1
        
        # 缩小窗口
        while window不满足条件:
            d = s[left]
            left += 1
            window[d] -= 1
        
        # 更新结果
        result = max(result, right - left + 1)
    
    return result

📚 LeetCode练习

对撞指针

快慢指针

滑动窗口

💻 完整代码实现

Python 实现

  1"""
  2双指针技巧实现
  3"""
  4
  5# ========== 对撞指针 ==========
  6
  7def two_sum_sorted(nums, target):
  8    """有序数组两数之和"""
  9    left, right = 0, len(nums) - 1
 10    
 11    while left < right:
 12        total = nums[left] + nums[right]
 13        if total == target:
 14            return [left, right]
 15        elif total < target:
 16            left += 1
 17        else:
 18            right -= 1
 19    
 20    return []
 21
 22
 23def three_sum(nums):
 24    """三数之和为0"""
 25    nums.sort()
 26    result = []
 27    
 28    for i in range(len(nums) - 2):
 29        # 去重
 30        if i > 0 and nums[i] == nums[i-1]:
 31            continue
 32        
 33        left, right = i + 1, len(nums) - 1
 34        while left < right:
 35            total = nums[i] + nums[left] + nums[right]
 36            if total == 0:
 37                result.append([nums[i], nums[left], nums[right]])
 38                # 去重
 39                while left < right and nums[left] == nums[left+1]:
 40                    left += 1
 41                while left < right and nums[right] == nums[right-1]:
 42                    right -= 1
 43                left += 1
 44                right -= 1
 45            elif total < 0:
 46                left += 1
 47            else:
 48                right -= 1
 49    
 50    return result
 51
 52
 53def container_with_most_water(height):
 54    """盛最多水的容器"""
 55    left, right = 0, len(height) - 1
 56    max_area = 0
 57    
 58    while left < right:
 59        width = right - left
 60        area = width * min(height[left], height[right])
 61        max_area = max(max_area, area)
 62        
 63        # 移动较短的那边
 64        if height[left] < height[right]:
 65            left += 1
 66        else:
 67            right -= 1
 68    
 69    return max_area
 70
 71
 72# ========== 快慢指针 ==========
 73
 74class ListNode:
 75    def __init__(self, val=0, next=None):
 76        self.val = val
 77        self.next = next
 78
 79
 80def has_cycle(head):
 81    """检测链表环"""
 82    slow = fast = head
 83    
 84    while fast and fast.next:
 85        slow = slow.next
 86        fast = fast.next.next
 87        if slow == fast:
 88            return True
 89    
 90    return False
 91
 92
 93def detect_cycle(head):
 94    """找环的起始节点"""
 95    slow = fast = head
 96    
 97    # 找相遇点
 98    while fast and fast.next:
 99        slow = slow.next
100        fast = fast.next.next
101        if slow == fast:
102            break
103    else:
104        return None
105    
106    # 找起始点
107    slow = head
108    while slow != fast:
109        slow = slow.next
110        fast = fast.next
111    
112    return slow
113
114
115def find_middle(head):
116    """找链表中点"""
117    slow = fast = head
118    
119    while fast and fast.next:
120        slow = slow.next
121        fast = fast.next.next
122    
123    return slow
124
125
126# ========== 滑动窗口 ==========
127
128def length_of_longest_substring(s):
129    """最长无重复字符子串"""
130    char_set = set()
131    left = 0
132    max_len = 0
133    
134    for right in range(len(s)):
135        while s[right] in char_set:
136            char_set.remove(s[left])
137            left += 1
138        char_set.add(s[right])
139        max_len = max(max_len, right - left + 1)
140    
141    return max_len
142
143
144def min_window(s, t):
145    """最小覆盖子串"""
146    from collections import Counter
147    
148    need = Counter(t)
149    window = {}
150    left = 0
151    valid = 0
152    start, length = 0, float('inf')
153    
154    for right in range(len(s)):
155        c = s[right]
156        window[c] = window.get(c, 0) + 1
157        
158        if c in need and window[c] == need[c]:
159            valid += 1
160        
161        while valid == len(need):
162            if right - left + 1 < length:
163                start = left
164                length = right - left + 1
165            
166            d = s[left]
167            left += 1
168            if d in need and window[d] == need[d]:
169                valid -= 1
170            window[d] -= 1
171    
172    return s[start:start + length] if length != float('inf') else ""
173
174
175def find_anagrams(s, p):
176    """找所有字母异位词"""
177    from collections import Counter
178    
179    need = Counter(p)
180    window = {}
181    left = 0
182    valid = 0
183    result = []
184    
185    for right in range(len(s)):
186        c = s[right]
187        window[c] = window.get(c, 0) + 1
188        
189        if c in need and window[c] == need[c]:
190            valid += 1
191        
192        while right - left + 1 >= len(p):
193            if valid == len(need):
194                result.append(left)
195            
196            d = s[left]
197            left += 1
198            if d in need and window[d] == need[d]:
199                valid -= 1
200            window[d] -= 1
201    
202    return result
203
204
205def demo():
206    """演示双指针"""
207    print("=== 双指针技巧演示 ===\n")
208    
209    # 两数之和
210    nums = [2, 7, 11, 15]
211    target = 9
212    print(f"两数之和 {nums}, target={target}:")
213    print(f"  结果: {two_sum_sorted(nums, target)}\n")
214    
215    # 三数之和
216    nums = [-1, 0, 1, 2, -1, -4]
217    print(f"三数之和 {nums}:")
218    print(f"  结果: {three_sum(nums)}\n")
219    
220    # 盛水
221    height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
222    print(f"盛最多水 {height}:")
223    print(f"  最大面积: {container_with_most_water(height)}\n")
224    
225    # 最长无重复子串
226    s = "abcabcbb"
227    print(f"最长无重复子串 '{s}':")
228    print(f"  长度: {length_of_longest_substring(s)}\n")
229    
230    # 字母异位词
231    s, p = "cbaebabacd", "abc"
232    print(f"找字母异位词 s='{s}', p='{p}':")
233    print(f"  起始索引: {find_anagrams(s, p)}")
234
235
236if __name__ == '__main__':
237    demo()
238

C++ 实现

  1/**
  2 * 双指针技巧实现
  3 */
  4
  5#include <iostream>
  6#include <vector>
  7#include <unordered_set>
  8#include <algorithm>
  9
 10using namespace std;
 11
 12// 两数之和（有序数组）
 13vector<int> twoSum(const vector<int>& nums, int target) {
 14    int left = 0, right = nums.size() - 1;
 15    
 16    while (left < right) {
 17        int sum = nums[left] + nums[right];
 18        if (sum == target) {
 19            return {left, right};
 20        } else if (sum < target) {
 21            left++;
 22        } else {
 23            right--;
 24        }
 25    }
 26    
 27    return {};
 28}
 29
 30// 三数之和
 31vector<vector<int>> threeSum(vector<int>& nums) {
 32    vector<vector<int>> result;
 33    sort(nums.begin(), nums.end());
 34    
 35    for (int i = 0; i < (int)nums.size() - 2; i++) {
 36        if (i > 0 && nums[i] == nums[i-1]) continue;
 37        
 38        int left = i + 1, right = nums.size() - 1;
 39        while (left < right) {
 40            int sum = nums[i] + nums[left] + nums[right];
 41            if (sum == 0) {
 42                result.push_back({nums[i], nums[left], nums[right]});
 43                while (left < right && nums[left] == nums[left+1]) left++;
 44                while (left < right && nums[right] == nums[right-1]) right--;
 45                left++;
 46                right--;
 47            } else if (sum < 0) {
 48                left++;
 49            } else {
 50                right--;
 51            }
 52        }
 53    }
 54    
 55    return result;
 56}
 57
 58// 盛最多水的容器
 59int maxArea(const vector<int>& height) {
 60    int left = 0, right = height.size() - 1;
 61    int maxWater = 0;
 62    
 63    while (left < right) {
 64        int width = right - left;
 65        int h = min(height[left], height[right]);
 66        maxWater = max(maxWater, width * h);
 67        
 68        if (height[left] < height[right]) {
 69            left++;
 70        } else {
 71            right--;
 72        }
 73    }
 74    
 75    return maxWater;
 76}
 77
 78// 最长无重复字符子串
 79int lengthOfLongestSubstring(const string& s) {
 80    unordered_set<char> charSet;
 81    int left = 0;
 82    int maxLen = 0;
 83    
 84    for (int right = 0; right < s.length(); right++) {
 85        while (charSet.count(s[right])) {
 86            charSet.erase(s[left]);
 87            left++;
 88        }
 89        charSet.insert(s[right]);
 90        maxLen = max(maxLen, right - left + 1);
 91    }
 92    
 93    return maxLen;
 94}
 95
 96int main() {
 97    cout << "=== 双指针技巧演示 ===" << endl << endl;
 98    
 99    // 两数之和
100    vector<int> nums = {2, 7, 11, 15};
101    int target = 9;
102    cout << "两数之和 [2,7,11,15], target=9:" << endl;
103    vector<int> indices = twoSum(nums, target);
104    cout << "  结果: [" << indices[0] << ", " << indices[1] << "]" << endl << endl;
105    
106    // 三数之和
107    vector<int> nums2 = {-1, 0, 1, 2, -1, -4};
108    cout << "三数之和 [-1,0,1,2,-1,-4]:" << endl;
109    vector<vector<int>> triplets = threeSum(nums2);
110    cout << "  结果: [";
111    for (size_t i = 0; i < triplets.size(); i++) {
112        cout << "[" << triplets[i][0] << "," << triplets[i][1] << "," << triplets[i][2] << "]";
113        if (i < triplets.size() - 1) cout << ", ";
114    }
115    cout << "]" << endl << endl;
116    
117    // 盛水
118    vector<int> height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
119    cout << "盛最多水 [1,8,6,2,5,4,8,3,7]:" << endl;
120    cout << "  最大面积: " << maxArea(height) << endl << endl;
121    
122    // 最长无重复子串
123    string s = "abcabcbb";
124    cout << "最长无重复子串 '" << s << "':" << endl;
125    cout << "  长度: " << lengthOfLongestSubstring(s) << endl;
126    
127    return 0;
128}