当前位置：首页 > article >正文

Java中双指针的介绍、分类及使用技巧示例

article 2024/12/23 13:36:25

一、前言

Java中的双指针是一种非常高效的算法技巧，它通过使用两个指针来遍历数组或字符串等数据结构，从而在一次遍历中找到符合条件的结果。下面将介绍Java双指针的基本概念、实现方式和应用场景。

二、双指针基础知识

双指针（Two Pointers）是指在遍历元素的过程中，不是使用单个指针进行访问，而是使用两个指针进行访问，从而达到相应的目的。

三、双指针的类型及示例

根据两个指针的移动方向和相对位置，双指针可以分为多种类型，如对撞指针、快慢指针、分离双指针等。

1、对撞指针

对撞指针是指两个指针分别从数组或字符串的两端开始，向中间移动，直到两个指针相撞或满足其他条件为止。对撞指针常用于查找有序数组中满足某些约束条件的一组元素问题，如二分查找、数字之和等问题，以及字符串反转问题。

‌示例代码‌：

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int low = 0;
        int high = numbers.length - 1;
        while (low < high) {
            int sum = numbers[low] + numbers[high];
            if (sum == target) {
                return new int[]{low + 1, high + 1};
            } else if (sum < target) {
                low++;
            } else {
                high--;
            }
        }
        return new int[]{-1, -1};
    }
}

2、快慢指针

快慢指针是指两个指针从同一侧开始遍历序列，且移动的步长一个快一个慢。快指针（fast）通常每次移动一步或两步，而慢指针（slow）每次只移动一步。快慢指针常用于处理数组中的移动、删除元素问题，或者链表中的判断是否有环、长度问题。

‌示例代码‌：

public class Solution {
    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;
    }
}

3、分离双指针

分离双指针是指两个指针分别属于不同的数组或链表，两个指针分别在两个数组或链表中移动。分离双指针常用于处理有序数组合并、求交集、并集等问题。

‌示例代码‌：

public class Solution {
    public int[] merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k] = nums1[i];
                i--;
            } else {
                nums1[k] = nums2[j];
                j--;
            }
            k--;
        }
        while (j >= 0) {
            nums1[k] = nums2[j];
            j--;
            k--;
        }
        return nums1;
    }
}

4、滑动窗口

滑动窗口是在给定数组或字符串上维护一个固定长度或不定长度的窗口。滑动窗口常用于解决一些查找满足一定条件的连续区间的性质（如长度等）的问题。

‌示例代码‌：

public class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        int left = 0;
        int sum = 0;
        int maxLength = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);

        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            if (map.containsKey(sum - k)) {
                maxLength = Math.max(maxLength, right - map.get(sum - k));
            }
            if (!map.containsKey(sum)) {
                map.put(sum, right);
            }
        }

        return maxLength;
    }
}

四、不同应用场景中的使用方式和优势

1、数组中的应用

‌查找满足条件的两个数‌：
- ‌应用场景‌：给定一个有序递增数组，在数组中找到满足条件的两个数，使得这两个数的和为某一给定的值。
- ‌应用方式‌：初始化两个指针，一个指向数组的第一个元素，另一个指向数组的最后一个元素。在两个指针相遇之前，根据当前两个指针所指元素和与给定数字的大小关系，移动指针以找到满足条件的两个数。
- ‌优势‌：通过双指针遍历法，可以在一次遍历中找到满足条件的两个数，时间复杂度为O(n)。
‌奇偶排序‌：
- ‌应用场景‌：给定一个数组，数组中元素有奇数有偶数，要求处理数组使得左边为奇数，右边为偶数。
- ‌应用方式‌：类似于快速排序的划分过程，使用双指针将奇数移动到数组的左侧，偶数移动到数组的右侧。
- ‌优势‌：无需额外的存储空间，直接在原数组上进行操作，时间复杂度为O(n)。

2、字符串中的应用

‌反转字符串‌：
- ‌应用场景‌：反转一个字符串。
- ‌应用方式‌：使用双指针分别指向字符串的头和尾，然后交换两个指针所指的字符，直到两个指针相遇。
- ‌优势‌：可以在原地反转字符串，无需额外的存储空间。
‌判断回文串‌：
- ‌应用场景‌：判断一个字符串是否是回文串。
- ‌应用方式‌：使用双指针分别指向字符串的头和尾，然后逐个比较两个指针所指的字符是否相同。
- ‌优势‌：只需一次遍历字符串即可判断是否为回文串，时间复杂度为O(n)。

3、链表中的应用

‌反转链表‌：
- ‌应用场景‌：反转一个单链表。
- ‌应用方式‌：使用三个指针，一个指向当前节点的前一个节点，一个指向当前节点，另一个指向当前节点的下一个节点。通过遍历链表并逐个反转节点的指针方向来实现链表的反转。
- ‌优势‌：可以在原地反转链表，无需额外的存储空间（除了几个用于遍历的指针）。
‌检测链表中的环‌：
- ‌应用场景‌：检测一个链表中是否存在环。
- ‌应用方式‌：使用快慢指针，快指针每次移动两步，慢指针每次移动一步。如果链表中存在环，则快慢指针最终会相遇。
- ‌优势‌：通过快慢指针的遍历方式，可以在O(n)的时间复杂度内检测链表中的环。
‌合并两个有序链表‌：
- ‌应用场景‌：合并两个有序链表为一个有序链表。
- ‌应用方式‌：使用双指针分别指向两个链表的头节点，然后逐个比较两个指针所指的节点的值，将较小的节点添加到新的链表中，并移动相应的指针。
- ‌优势‌：可以在O(n)的时间复杂度内合并两个有序链表，其中n是两个链表中节点的总数。