发表计算机 / 数据结构与算法11 分钟读完 (大约1709个字)

双指针算法

双指针是一种重要的算法技巧，使用两个指针对数组或链表进行操作。

一、对撞指针

对撞指针是指两个指针从数组的两端向中间移动。

1. 经典问题：两数之和

给定一个已按照升序排列的数组，找出两个数使得它们的和等于目标数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int[] twoSum(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return new int[]{left, right};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return new int[]{-1, -1};
}

解题思路：

  • 在排序数组中，当sum > target时，右指针左移可以减小和
  • 当sum < target时，左指针右移可以增大和
  • 时间复杂度：O(n)，比暴力解法O(n²)更优

2. 盛最多水的容器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int maxArea = 0;
    
    while (left < right) {
        int area = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, area);
        
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxArea;
}

解题思路：

  1. 面积计算：min(h[i], h[j]) * (j-i)
  2. 移动策略：
    • 每次移动短板
    • 因为宽度一定减小，只有通过增加高度才可能得到更大面积
    • 移动长板只会使面积更小或不变

二、快慢指针（同向双指针）

两个指针同向移动，但速度不同。

1. 删除排序数组中的重复项

1
2
3
4
5
6
7
8
9
10
11
public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int slow = 0;
    for (int fast = 1; fast < nums.length; fast++) {
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1;
}

原理分析：

  • slow指针：指向当前无重复数组的末尾
  • fast指针：探索新的不重复元素
  • 时间复杂度：O(n)，空间复杂度：O(1)

2. 移动零

将所有0移到数组末尾，同时保持非零元素的相对顺序。

1
2
3
4
5
6
7
8
9
10
11
public void moveZeroes(int[] nums) {
    int nonZore = -1, zore = 0;
    while(zore < nums.length) {
        if (nums[zore] != 0 && ++nonZore != zore) {
            nums[zore] = nums[zore] ^ nums[nonZore];
            nums[nonZore] = nums[zore] ^ nums[nonZore];
            nums[zore] = nums[zore] ^ nums[nonZore];
        }
        zore++;
    }
}

算法思想：

  • nonZero指针：指向下一个非零元素应该放置的位置
  • i指针：遍历数组寻找非零元素
  • 保证nonZero左侧都是非零元素，且保持原序

3. 求数组/链表上中点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }

public class FindMiddle {
    public ListNode findMiddle(ListNode head) {
        if (head == null) {
            return null; // 空链表
        }
        
        ListNode slow = head;
        ListNode fast = head.next; // 从第二个节点开始

        while (fast != null && fast.next != null) {
            slow = slow.next;         // 慢指针每次移动一步
            fast = fast.next.next;   // 快指针每次移动两步
        }

        return slow; // 返回上中点
    }

    public static void main(String[] args) {
        FindMiddle finder = new FindMiddle();
        
        // 测试用例 1: 空链表
        ListNode test1 = null;
        System.out.println("Test 1: " + (finder.findMiddle(test1) == null ? "null" : finder.findMiddle(test1).val));

        // 测试用例 2: 单个节点
        ListNode test2 = new ListNode(1);
        System.out.println("Test 2: " + finder.findMiddle(test2).val); // 应返回 1

        // 测试用例 3: 两个节点
        ListNode test3 = new ListNode(1);
        test3.next = new ListNode(2);
        System.out.println("Test 3: " + finder.findMiddle(test3).val); // 应返回 1（上中点）

        // 测试用例 4: 奇数个节点
        ListNode test4 = new ListNode(1);
        test4.next = new ListNode(2);
        test4.next.next = new ListNode(3);
        System.out.println("Test 4: " + finder.findMiddle(test4).val); // 应返回 2

        // 测试用例 5: 偶数个节点
        ListNode test5 = new ListNode(1);
        test5.next = new ListNode(2);
        test5.next.next = new ListNode(3);
        test5.next.next.next = new ListNode(4);
        System.out.println("Test 5: " + finder.findMiddle(test5).val); // 应返回 2（上中点）

        // 测试用例 6: 多个节点
        ListNode test6 = new ListNode(1);
        test6.next = new ListNode(2);
        test6.next.next = new ListNode(3);
        test6.next.next.next = new ListNode(4);
        test6.next.next.next.next = new ListNode(5);
        System.out.println("Test 6: " + finder.findMiddle(test6).val); // 应返回 3

        // 测试用例 7: 较长的链表
        ListNode test7 = new ListNode(1);
        for (int i = 2; i <= 10; i++) {
            ListNode newNode = new ListNode(i);
            ListNode current = test7;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
        System.out.println("Test 7: " + finder.findMiddle(test7).val); // 应返回 5
    }
}

三、滑动窗口

滑动窗口是双指针的特殊形式，维护一个可变大小的窗口。

1. 最小覆盖子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public String minWindow(String s, String t) {
    if (s == null || t == null || s.length() < t.length()) return "";
    
    int[] map = new int[128];
    for (char c : t.toCharArray()) {
        map[c]++;
    }
    
    int start = 0, minStart = 0, minLen = Integer.MAX_VALUE;
    int count = t.length();
    
    for (int end = 0; end < s.length(); end++) {
        if (map[s.charAt(end)] > 0) {
            count--;
        }
        map[s.charAt(end)]--;
        
        while (count == 0) {
            if (end - start + 1 < minLen) {
                minLen = end - start + 1;
                minStart = start;
            }
            
            map[s.charAt(start)]++;
            if (map[s.charAt(start)] > 0) {
                count++;
            }
            start++;
        }
    }
    
    return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
}

滑动窗口原理：

  1. 扩展窗口：右指针右移，直到包含所有目标字符
  2. 收缩窗口：左指针右移，直到不满足条件
  3. 记录最优解：在每次找到可行解时更新

2. 最长无重复子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int lengthOfLongestSubstring(String s) {
    int[] lastIndex = new int[128];
    Arrays.fill(lastIndex, -1);
    
    int maxLen = 0;
    int start = 0;
    
    for (int end = 0; end < s.length(); end++) {
        char c = s.charAt(end);
        start = Math.max(start, lastIndex[c] + 1);
        maxLen = Math.max(maxLen, end - start + 1);
        lastIndex[c] = end;
    }
    
    return maxLen;
}

算法分析：

  • start维护无重复子串的起始位置
  • lastIndex记录每个字符最后出现的位置
  • 当发现重复字符时，start跳转到重复字符上次出现位置的下一位

四、多指针技巧

1. 三数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    // 排序，答案不要保持原有顺序，排序好处 a + b = c，此时 a < b < c
    Arrays.sort(nums);
    // 固定i后，退化为双指针
    for (int i = 0; i < nums.length - 2; i++) {
        // 跳出特殊条件：答案不能重复 a + b = c, a != b
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        // 左右指针和答案
        int left = i + 1, right = nums.length - 1, target = -nums[i];
        // 开始移动
        while (left < right) {
            // 答案
            int sum = nums[left] + nums[right];
            if (sum == target) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                // 移动到下一个不相同的数为止
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                // 继续缩小范围
                left++;
                right--;
            } else if (sum < target) {
                // 已经排过序，所以和<答案，就移动左，增大
                left++;
            } else {
                // 同上
                right--;
            }
        }
    }
    return result;
}

算法要点：

  1. 排序是关键：便于去重和移动指针
  2. 固定一个数，转化为两数之和
  3. 去重处理：
    • 对第一个数去重
    • 对左右指针去重

五、双指针的时间复杂度分析

  1. 对撞指针：

    • 典型时间复杂度：O(n)
    • 空间复杂度：O(1)

  2. 快慢指针：

    • 时间复杂度：O(n)
    • 空间复杂度：O(1)

  3. 滑动窗口：

    • 时间复杂度：O(n)
    • 空间复杂度：取决于具体问题，通常是O(1)或O(k)

  4. 多指针：

    • 时间复杂度：通常是O(n²)
    • 空间复杂度：除去输出，通常是O(1)

总结

双指针技巧的核心思想是：

  1. 通过控制两个或多个指针的移动来降低时间复杂度
  2. 在线性数据结构中寻找特定模式或关系
  3. 通常能将暴力解法的时间复杂度从O(n²)优化到O(n)

使用双指针时的关键考虑点：

  1. 指针的初始位置
  2. 指针的移动条件
  3. 结果的更新时机
  4. 特殊情况的处理
  5. 去重的必要性
#

最新文章

分类

标签

CentOS2
Docker1
Dubbo7
JDBC1
JPMS1
JVM3
Kafka1
LLM1
MySQL1
Nacos21
Seata13
Sentinel18
Spring Cloud39
Spring Cloud Alibaba66
Spring Cloud Gateway6
Stable Diffusion2
TCP/IP1
ZooKeeper19
gcc1
modules1
mysql1
nginx1
nio1
分布式10
分布式事务14
加密1
基础672
多线程1
安全2
应用层1
数据库2
数据结构与算法36
方案1
源码解析18
知识点22
缓存1
网络1
设计模式25
语法1
调优2
集合4
面试题2
×