Java双指针技巧

2023-03-14 17:55:16

在我们练习Java算法的时候，难免会遇到一些题目利用一些技巧性的解题方法比不用要强很多，这次主要分享一下有关双针的技巧。

双指针一般分为两类：一类是快慢指针，一类是左右指针。前者解决主要链表中的问题，比如典型的判断链表中是否包含环；后者主要解决数组（或字符串）中的问题，比如二分查找。

一、快慢指针

1. 判断链表中是否含有环

链表中要想不含环，那么这个指针最终会遇到空指针 null 表示链表到头了，这还好说，可以判断该链表不含环

boolean hasCycle(ListNode head) {
    while (head != null) {
        head = head.next;
    }
    return false;
}

如果链表中存在环了，那么上述的代码就会陷入死循环，因为环形数组中没有 null 指针作为尾部节点。

经典解法就是用两个指针，一个跑的快，一个跑的慢，如果不含有环，跑的快的那个指针最终会遇到 null，说明链表不含有环。如果快指针最终会超满指针一圈，和慢指针相遇，说明链表含有环。

boolean hasCycle(ListNode head) {
    ListNode fast = head, slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        // 如果两个指针相遇，说明构成了环，返回 true
        if (fast = slow) {
            return true;
        }
    }
    return false;
}

2. 已知链表中含有环，返回这个环的起止位置

ListNode detectCycle(ListNode head) {
    ListNode fast = head, slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (slow = fast) {
            break;
        }
    }
    if (fast == null || fast.next == null) {
        // fast 没有遇到环，遇到了空指针
        return null;
    }
    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

当快慢指针相遇的时候，让其中一个指针指向头节点，然后再让快慢指针以相同的速度前进，再次相遇的时候，就是环开始的位置。

解释：

第一次相遇时，假设慢指针 slow 走了 k 步，那么快指针 fast 一定走了 2k 步；

fast 一定比 slow 多走了 k 步，这多走的 k 步其实就是 fast 指针在环里转圈圈，所以 k 的值就是环长度的整数倍。

假设相遇点距离环的起点的距离为 m ，那么环的起点距头节点 head 的距离就是 k - m，也就是说如果从 head 前进 k - m 步就能到达环起点。

巧的是，如果从相遇点继续前进 k - m 步，也恰好到达环起点，甭管 fast 在环里转了几圈，走 k 步到相遇点，那走 k - m 步一定就是走到环起点了

所以，只要我们把快慢指针中的任一重新指向 head，然后两个指针同速前进，k - m 步就会相遇，相遇之处就是环的起点了。

二、左右指针

左右指针在数组中实际上是指两个索引值，一般初始化为 left = 0, right = nums.length - 1

1. 二分查找

int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = (right + left) / 2;
     	if (nums[mid] == target) {
            return mid;
        }
        if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        }
    }
    return - 1;
}

2. 两数之和

只要数组有序，我们就应该想到双指针的技巧，

int[] twoSum(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return new int[]{left, right}
        } else if (sum < target) {
            // 让 sum 大一些
            left++;
        } else if (sum > target) {
            // 让 sum 小一些
            right--;
        }
    }
    return new int[]{-1, -1};
}

3. 数组反转

反转一个 char[] 类型的字符串数组

void reverseString(char[] arr) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        arr[left] = arr[left] + arr[right];
        arr[right] = arr[left] - arr[right];
        arr[left] = arr[left] - arr[right];
        left++;
        right--;
    }
}

如果这几个例子可以掌握了，那么双指针基本的思想，以及链表等基本操作也就可以掌握了，掌握了基本的技巧，还需要经过做一些题目进行打磨，多写一些题目会更加深刻的理解。

码农公寓