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

双指针技术是一种非常高效的算法设计模式，特别适用于解决一些在数组或链表中需要进行搜索和排序的问题。双指针技术通常可以帮助我们将时间复杂度降至O(n)，从而提高算法的运行效率。本文将重点介绍双指针的应用场景及其在Java中的实现方式。

什么是双指针？

双指针技术通常涉及使用两个指针分别从数组的两端或中间向对方移动。根据移动的方式，这种技术可以分为以下几类：

1. 对撞指针：两个指针分别从数组的两端朝中间移动。
2. 快慢指针：一个指针每次移动一步，另一个指针每次移动两步，常用在链表的相关问题。
3. 滑动窗口：动态调整指针，使其覆盖某个有效范围内的元素，常用于子数组或子串的查找问题。

应用场景

1. 有序数组的两数之和： 在已排序的数组中，寻找和为特定值的两个数。

2. 删除排序数组中的重复项：
   在一个已排序的数组中，去除重复元素并返回新的数组长度。

3. 反转字符串： 用两个指针分别指向字符串的开头和结尾，交换字符，直到两个指针重合。

接下来，我们将通过代码示例来详细说明这些应用。

例子1：有序数组的两数之和

public class TwoSum {
    public static 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) {
        int[] numbers = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSum(numbers, target);
        System.out.println("Result: " + result[0] + ", " + result[1]);
    }
}

例子2：删除排序数组中的重复项

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

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                nums[uniqueIndex] = nums[i];
                uniqueIndex++;
            }
        }
        return uniqueIndex; // 返回新数组的长度
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 2};
        int length = removeDuplicates(nums);
        System.out.println("New length: " + length);
        // 打印不重复的元素
        for (int i = 0; i < length; i++) {
            System.out.print(nums[i] + " ");
        }
    }
}

例子3：反转字符串

public class ReverseString {
    public static void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;

        while (left < right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }

    public static void main(String[] args) {
        char[] str = {'h', 'e', 'l', 'l', 'o'};
        reverseString(str);
        System.out.println(str); // 输出: "olleh"
    }
}

总结

双指针技术是一种非常实用的算法策略，能够有效优化算法的时间复杂度，适用于多种问题场景。在实际开发中，理解并掌握双指针的应用方法，将有助于提高代码质量和性能。在解决问题时，不妨尝试将问题转换为双指针问题，从而简化解决方案。