【Java 优选算法】双指针(上)

双指针技术是解决许多算法问题的一种高效方法，尤其常用于数组和链表的操作。它使用两个指针同时在数据结构上移动，以达到简化问题和提高效率的目的。双指针法的基本思想是通过两个指针分别处理数据中的不同部分，减少不必要的遍历，从而加快计算速度。

双指针的基本应用

双指针技术主要有两种形式：一种是“快慢指针”，另一种是“左右指针”。下面我们分别介绍这两种形式。

1. 快慢指针

快慢指针通常用于链表问题，尤其是在寻找环和中间节点时非常有效。快指针移动速度较快，通常每次移动两步，而慢指针移动较慢，每次移动一步。这样，可以有效检测链表中是否存在环，或者找到链表的中间节点。

示例：判断链表是否有环

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        ListNode slow = head;
        ListNode fast = head.next; // fast 从 head.next 开始

        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

在上述代码中，slow指针每次移动一位，fast指针每次移动两位。如果链表中存在环，则最终两者会相遇；如果不存在，则fast指针会遍历到链表末尾，返回false。

2. 左右指针

左右指针常用于处理数组的问题，特别是在排序、去重、寻找特定的数和和的目标等场景。通过调整两个指针的位置，可以优化求解过程，从而达到所需的效果。

示例：两数之和

假设我们要在一个已排序的数组中找到两个数，使它们的和等于给定的目标值。可以使用左右指针的办法，从数组两端向中间逼近。

public class TwoSum {
    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是为了符合题目的输出要求
            } else if (sum < target) {
                left++; // 增加左指针
            } else {
                right--; // 减小右指针
            }
        }
        return new int[]{-1, -1}; // 如果没有找到
    }
}

在这个例子中，我们开始时分别从数组的最左和最右两端开始，计算它们的和，根据和与目标值的大小关系来调整指针的移动方向。这个过程可以在O(n)的时间复杂度下完成。

总结

双指针技术是一种灵活而高效的算法策略，简化了许多复杂问题的求解过程。通过适当地定位指针的移动，可以在许多场合下显著减少时间复杂度，提高程序执行效率。无论是在链表处理还是数组求解中，合理运用双指针思维都能帮助我们快速找到问题的解决方案。