双指针算法是一种常见且高效的算法思想，广泛应用于数组、字符串等线性结构中。其基本理念是使用两个指针在数据结构上同时移动，以达到高效遍历与处理数据的目的。双指针算法在解决很多具体问题时非常有效，如数组中的两数之和、子数组问题、链表问题等。
基本思想
双指针算法的核心思想是使用两个指针来迭代数据结构，这两个指针可以同步移动（如滑动窗口），也可以以不同步的方式移动（如快慢指针）。根据具体问题的需求，双指针可以用于：
1. **滑动窗口**：用于寻找满足某一条件的子数组或子字符串。
2. **快慢指针**：用于检测链表中的环或确定链表的中间节点。
3. **对撞指针**：用于处理排序数组中的问题，如两数之和等。
常见应用场景及代码示例
1. 滑动窗口
滑动窗口常用于求解数组或字符串中的子数组或子字符串问题，如最长无重复子串、最小覆盖子串等。
**示例问题：找到字符串中不含重复字符的最长子串长度。**
```java import java.util.HashSet; import java.util.Set; public class LongestSubstringWithoutRepeatingCharacters { public int lengthOfLongestSubstring(String s) { Set<Character> set = new HashSet<>(); int maxLength = 0; int left = 0; for (int right = 0; right < s.length(); right++) { while (set.contains(s.charAt(right))) { set.remove(s.charAt(left)); left++; } set.add(s.charAt(right)); maxLength = Math.max(maxLength, right - left + 1); } return maxLength; } public static void main(String[] args) { LongestSubstringWithoutRepeatingCharacters solution = new LongestSubstringWithoutRepeatingCharacters(); String s = "abcabcbb"; System.out.println(solution.lengthOfLongestSubstring(s)); // Output: 3 ("abc") } } ```
2. 快慢指针
快慢指针常用于链表问题，如判断链表是否有环、寻找链表的中间节点等。
**示例问题：判断链表中是否有环。**
```java class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } } public class LinkedListCycle { public boolean hasCycle(ListNode head) { if (head == null || head.next == null) { return false; } ListNode slow = head; ListNode fast = head.next; while (slow != fast) { if (fast == null || fast.next == null) { return false; } slow = slow.next; fast = fast.next.next; } return true; } public static void main(String[] args) { LinkedListCycle solution = new LinkedListCycle(); ListNode head = new ListNode(3); head.next = new ListNode(2); head.next.next = new ListNode(0); head.next.next.next = new ListNode(-4); head.next.next.next.next = head.next; System.out.println(solution.hasCycle(head)); // Output: true } } ```
3. 对撞指针
对撞指针通常用于排序数组中的问题，如两数之和、三数之和等。
**示例问题：在排序数组中查找两数之和等于目标值的两个数。**
```java public class TwoSumSortedArray { public int[] twoSum(int[] numbers, int target) { int left = 0; int right = numbers.length - 1; while (left < right) { int sum = numbers[left] + numbers[right]; if (sum == target) { return new int[]{left + 1, right + 1}; // 返回1-based索引 } else if (sum < target) { left++; } else { right--; } } return new int[]{-1, -1}; // 表示未找到 } public static void main(String[] args) { TwoSumSortedArray solution = new TwoSumSortedArray(); int[] numbers = {2, 7, 11, 15}; int target = 9; int[] result = solution.twoSum(numbers, target); System.out.println(result[0] + ", " + result[1]); // Output: 1, 2 } } ```
总结
双指针算法是一种简单而强大的工具，能够大幅提高解决特定类型问题的效率。通过合理地使用两个指针，我们可以在许多情况下将时间复杂度从O(n^2)降低到O(n)。理解并熟练掌握双指针技巧，对提升编码能力和算法水平具有重要意义。
