双指针基本使用 / 对撞指针 / 滑动窗口 / 快慢指针 

概述

题目序号为leetcode编号。

本质为分别使用两个指针以某种规则分别去指向数据。有时候也可以使用双指针去优化一些O(n^2)的算法。这些算法我认为的最重要的特点是，思路以及代码实现很简单，但自己短时间之内却想不到这样的解决方案.

283.移动零

使用指针k指向一个为0的位置，当i移动到后面非0数字的时候，和k相交换。最后再以k为起点全部赋值为0.

public void moveZeroes(int[] arr) {
    int k = 0;
    for(int i = 0; i < arr.length; i++){
        if(arr[i] != 0){
            arr[k++] = arr[i];
        }        
    }
    for(int i = k; i < arr.length; i++){
        arr[i] = 0;
    }
}

3.无重复字符的最长子串

主要思路是以j为基准，看i往右边在保持重复为1的情况下i和j能有多长。如果i重复次数>1，代表i无法再继续往右延申。那么j只能来到i的位置。通过每次比较，最终得到result。复杂度为O(n)。

public int lengthOfLongestSubstring(String s) {
    int[] r = new int[128];
    int result = 0;

    for(int i = 0, j = 0; i < s.length(); i++){
        r[s.charAt(i)]++;
        while(r[s.charAt(i)] > 1) {
            r[s.charAt(j)]--;
            j++;
        }
        result = Math.max(result, i - j + 1);
    }
    return result;
}

167.两数之和 II - 输入有序数组(对撞指针)

这题我的第一个思路是使用二分去寻找 (target - i), 虽然ac了，但效率并不高。

以下代码主要思路为，借助题目数组为有序的特性，使用i在前，j在后，逐个进行向中试探。

public int[] twoSum(int[] arr, int target) { 
    int i = 0;
    int j = arr.length - 1;
    while(true){
        if(i == j) return new int[]{};
        int t = arr[i] + arr[j];
        if(t == target){
            return new int[]{i + 1, j +  1};
        }
        else if(t > target) j--;
        else i++;  
    }  
}

209. 长度最小的子数组(滑动窗口)

在O(n)的状态下解决问题。

public int minSubArrayLen(int target, int[] nums) {
    int i = 0, j = -1;
    int sum = 0;
    int result = 0;
    while(i < nums.length){
        if(j + 1 < nums.length && sum < target){
            sum += nums[++j];            
        }else{
            int t = j - i + 1;
            if(result == 0) result = t;
            else{
                 result = Math.min(result, t);
            }               
            sum -= nums[i++];
        }
    }
    return result;       
}

141.环形链表(快慢指针)

使用快慢指针。快指针每次走两步，而慢指针走一步。如果链表中出现环，快指针必然会与慢指针相遇。

public boolean hasCycle(ListNode head) {
    ListNode t = head;
    if(t == null || t.next == null) return false;
    if(t.next.equals(t)) return true;
    
    ListNode fastNode = t;
    ListNode lowNode = t;
   
    while(fastNode.next != null && fastNode.next.next != null && lowNode.next != null){
        fastNode = fastNode.next.next;
        lowNode = lowNode.next;
        if(fastNode.equals(lowNode)){
            return true;
        }
        
    }
    return false;
}