【Java版算法思想】双指针算法_双指针算法java

一、什么是双指针算法？

严格的来说，双指针只能说是是算法中的一种技巧。

双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。

二、双指针算法的适用范围

常用在数组遍历中，我们使用两个指针进行操作，遍历完整个数组来实现我们的目的。一般能用双指针算法解决的问题，都可以用暴力解法解决，常用于单调场景。所以双指针问题基本有以下几个细节：

1、注意双指针的初始位置。
2、注意双指针的移动方法。
3、注意遍历的结束条件。
1
2
3

三、顺序双指针和对撞双指针

顺序双指针指的是2个指针的遍历方向相同，常用于数组的拼接等场景。

对撞双指针是指2个指针从两头向中间进行数组遍历，快速排序就是典型的双指针问题。

代码实现：

我们假设数组名字为 nums，数组长度为 n，数组首元素对应的位置为 0，尾元素对应的位置为 n-1

顺序双指针的实现过程就是每次把数组的首指针++ 或 尾指针- -，例如Leecode88.合并2个数组，https://leetcode-cn.com/problems/merge-sorted-array/，分别同时从头遍历2个数组或从尾遍历2个数组，结束条件为2个指针同时越界即可。

这里贴出双指针头遍历和尾遍历的代码实现：

    /**
     * 0 1 2 3 4 5
     * nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
     * 每次从两个数组头部取出比较小的数字放到结果中
     */
    public void merge0(int[] nums1, int m, int[] nums2, int n) {
        int p1 = 0, p2 = 0;
        int[] sorted = new int[m + n];
        int cur;
        // 双指针结束条件
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                // 端口位置特殊判断, p1已经遍历完就继续遍历p2
                cur = nums2[p2++];
            } else if (p2 == n) {
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {
                // p1小,p1入队,p1++
                cur = nums1[p1++];
            } else {
                // p2小,p2入队,p2++
                cur = nums2[p2++];
            }
            sorted[p1 + p2 - 1] = cur;
        }
        for (int i = 0; i < m + n; i++) {
            nums1[i] = sorted[i];

        }
    }

    /**
     * 0 1 2 3 4 5
     * nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
     * 每次从两个数组尾部取出比较大的数字放到结果中
     */
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1;
        int p2 = n - 1;
        int cur;
        while (p1 > 0 || p2 > 0) {
            if (p1 == 0) {
                cur = nums2[p2--];
            } else if (p2 == 0) {
                cur = nums1[p1--];
            } else if (nums1[p1] > nums2[p2]) {
                cur = nums1[p1--];
            } else {
                cur = nums2[p2--];
            }
            nums1[p1 + p2 + 2] = cur;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

对撞双指针我们一般需要设置2个指针分别指向最数组左端点和右端点

左指针（left)一般指向数组的第一个元素。即 left = 0。

右指针（right)一般指向数组的第一个元素。即 right = n-1。

指针移动方法：

左指针(left）向右边