[数据结构与算法]双指针的应用

双指针的应用

一. 双指针可分为：快慢指针，对撞指针。
二. 双指针技巧主要应用在解决 数组，链表 以及 字符串 问题
三. 双指针的应用场景：
（1）快慢指针：主要运用于处理链表内部环路的问题，再就是可以解决数组内是否有重复项的问题。
eg-1. 删除有序数组中的重复项（leetcode 第26题 - 难度 easy）

class Solution {
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if(len == 0 || len == 1){
            return len;
        }
        int slow = 0;
        for(int fast=0;fast<len;fast++){
            if(nums[fast] != nums[slow]){
                nums[++slow] = nums[fast];
            }
        }
        return slow+1;
    }
}

思路：快指针一直走，如果（快指针指向的值）==（慢指针指向的值）则直接跳过，而（快指针指向的值）！=（慢指针指向的值）则让慢指针先向前移动一位，再让让（快指针指向的值）把（慢指针指向的值）覆盖，最终得到删除重复元素的数组。

eg-2. 判断链表内部是否有环（leetcode 第141题 - 难度 easy）

public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null){
            return false;
        }
        ListNode slow, fast;
        slow = fast = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }
}

思路：快指针走得快，慢指针走得慢，若链表中存在环路，则两指针一定会相遇，并且快指针会快慢指针一周（经典的相遇问题）；若链表中不存在环路，则快指针一定会指向null。

（2）对撞指针：主要运用于处理数组和字符串的索引问题.
eg-1. 两数之和 II - 输入有序数组(leetcode 第167题 - 难度 easy)
(twoSum问题也可以用HashMap 或者 HashSet 帮助我们处理?序数组相关的简单问题)

public int[] twoSum(int[] numbers, int target) {
        int len = numbers.length;
        int left = 0;
        int right = len - 1;
        while(left < right){
            if(numbers[left] + numbers[right] > target){
                right--;
            }
            else if(numbers[left] + numbers[right] < target){
                left++;
            }
            else{
                int[] arr = new int[2];
                arr[0] = left + 1;
                arr[1] = right + 1;
                return arr;
            }
        }
        return null;
    }

思路: 左右两个指针分别指向数组的头和尾, 若 (两指针指向的值的和) > (target) 则让右指针左移一位, 若 (两指针指向的值的和) < (target) 则让左指针右移一位,找到target值后最终返回 左右指针的索引.

eg-2. 验证回文字符串(leetcode 第167题 - 难度 easy)

public boolean isPalindrome(String s) {
        String str = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
        char[] arr = str.toCharArray();
        int len = arr.length;
        int left = 0;
        int right = len - 1;
        while(left < right){
            if(arr[left] != arr[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

都差不多,这里就不多赘述,要注意一下replaceAll的使用和正则表达式.