算法【Java】—— 双指针算法

双指针算法是一种常用的算法技巧，特别适用于处理数组或链表等线性结构中的问题。它通过维护两个指针（通常是数组中的两个索引）来遍历数据，从而有效地降低时间复杂度，提高性能。这种方法常见于排序、搜索、组合等问题中。

双指针算法的基本思想

双指针算法的基本思想是使用两个指针分别指向数组的不同位置，通过移动这两个指针来达到某种目的。具体的实现方式可以激发出不同类型的问题解决方案。常见的双指针类型有：

1. 相向指针（头尾指针）：一个指针从数组的开头开始，另一个指针从数组的末尾开始，朝向中心移动，常用于寻找配对问题或判断是否对称等。

2. 左指针和右指针：两个指针从同一方向开始，一个指针负责遍历，另一个指针用于记录特定条件下的位置，常用于去重或划分等。

示例代码

下面是一个典型的双指针算法的例子，给出一个具体问题的解决方案：给定一个排序数组，去除重复元素，并返回新的长度。

public class RemoveDuplicates {
    public static int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        // 初始化双指针
        int left = 0;  // 快指针
        int right = 1; // 慢指针

        while (right < nums.length) {
            // 如果快指针的值与慢指针的值不同，则更新慢指针
            if (nums[right] != nums[left]) {
                left++;
                nums[left] = nums[right]; // 将不同的元素放到左边
            }
            right++; // 快指针一直向右移动
        }

        // 返回新数组的长度
        return left + 1; // 因为下标从0开始，所以返回的长度是left + 1
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 2, 2, 3, 4, 5, 5};
        int newLength = removeDuplicates(nums);

        System.out.println("新的数组长度: " + newLength);
        System.out.print("去重后的数组: ");
        for (int i = 0; i < newLength; i++) {
            System.out.print(nums[i] + " ");
        }
    }
}

代码解析

在上述代码中，removeDuplicates方法通过双指针来去除排序数组中的重复元素。left指针用于保留不重复元素的位置，而right指针用来遍历整个数组。当发现right指针所指向的元素与left指针所指向的元素不同时，就将新的元素放到left指针下一个位置，并且移动left指针。最后返回的是不重复元素的新长度。

应用场景

双指针算法的应用场景非常广泛，例如：

• 在排序数组中查找两个数的和；
• 在链表中寻找中间节点；
• 在数组中寻找三元组之和等；
• 判断链表是否存在环；
• 合并两个排序链表等。

结论

双指针算法是一种简单而有效的算法技巧，适用于多种场景。通过合理地使用双指针，可以显著提高算法的效率，尤其是在处理线性结构的问题时。掌握这种算法有助于提升算法解题能力和思维方式，是程序员不可或缺的技能之一。