本文共 7337 字，大约阅读时间需要 24 分钟。

双指针

双指针也是所谓滑动窗口算法。

一般用于求解具有某种特质的子数组、子字符串、链表查询的分隔问题，通过两个指针来标识窗口的边界（子数组、子字符串、链表标记）。

顾名思义，有2个指针，头指针和尾指针(窗口边界)，结合while使用。二分也是利用双指针的思想。

import java.util.HashMap;import java.util.HashSet;import java.util.Map;import java.util.Set;/** * Title：NC41-最长无重复, 数组中最长连续无重复长度 * Description：双指针、Set、Map * @author WZQ * @version 1.0.0 * @date 2021/2/24 */public class NC41 {
       /**     * @param arr int整型一维数组 the array     * @return int整型     */    public int maxLength (int[] arr) {
           int length = arr.length;        if (length < 2){
               return length;        }        // 双指针        // j纪录尾部，遍历到尾部        // i纪录头部，遇到重复的向后遍历删除        int max = 0, i = 0, j = 0;//        Map
   
     map = new HashMap<>();//        while (j < length){
   //            //包含//            if (map.containsKey(arr[j])){
   //                //存在相同的元素//                // 123412 1234 i=0 j=4,//                i = map.get(arr[j])//            }else {
   //                //不包含//                map.put(arr[j], j);//            }//            max = Math.max(max, j - i + 1);//            j++;//        }        Set
    
      set = new HashSet<>();        while (j < length){
               //包含            if (set.contains(arr[j])){
                   //头指针, 删除到重复元素的下一个位置                set.remove(arr[i]);                i ++;            }else {
                   //不包含                set.add(arr[j]);                j ++;            }            max = Math.max(max, set.size());        }        return max;    }}
    
   

/** * Title：NC22-合并2个有序数组, 不能开辟额外的空间，结果存放在A数组中 * Description：双指针 * @author WZQ * @version 1.0.0 * @date 2021/3/3 */public class NC22 {
       public static void merge(int A[], int m, int B[], int n) {
           //双指针，纪录2个集合确定合并的位置        int a = 0, b = 0, temp = 0;        while (a < (m+n) && b < n){
               //小于，A[a]位置不变            while (a < (m+b) && A[a] < B[b]){
                   a ++;            }            //等于，大于，A[a]后未判断的全体后退            if (m + b - a >= 0) System.arraycopy(A, a, A, a + 1, m + b - a);//            for (int i = m+b-1; i>=a; i--) {
   //                A[i+1] = A[i];//            }            //B[b]放到A[a]位置            A[a] = B[b];            a ++;            b ++;        }    }    /**     * 1 3 7     * 1 5 6     * 1 1 3 5 6 7     *     * @param args     */    public static void main(String[] args) {
           int[] arr1 = {
   1, 3, 7, 0, 0, 0};        int[] arr2 = {
   1, 5, 6};        merge(arr1, arr1.length/2, arr2, arr2.length);    }}

import java.util.HashMap;import java.util.Map;/** * Title：leetcode-76. 最小覆盖子串 * Description：滑动窗口+Hash * * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。 * 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。 *  * @author WZQ * @version 1.0.0 * @date 2021/3/26 */public class Main76 {
       public String minWindow(String s, String t) {
           String res = "";        // 窗口，统计字符的方式        Map
   
     window = new HashMap<>();        // 子串t字符统计        Map
    
      chars = new HashMap<>();        int tLen = t.length();        int sLen = s.length();        for (int i = 0; i < tLen; i++) {
               chars.put(t.charAt(i), chars.getOrDefault(t.charAt(i), 0) + 1);        }        // 双指针, left到right窗口长度 > tLen开始check        int left = 0, right = 0, min = Integer.MAX_VALUE;        while (right < sLen) {
               char ch = s.charAt(right);            // 纪录到窗口            window.put(ch, window.getOrDefault(ch, 0) + 1);            // check成功，则left向后，压缩窗口，直到check失败，纪录min，right接着向后，依次类推            while (check(window, chars)) {
                   if ((right - left + 1) < min) {
                       min = right - left + 1;                    res = s.substring(left, right + 1);                }                // left向后压缩窗口                char ch2 = s.charAt(left);                window.put(ch2, window.get(ch2) - 1);                if (window.get(ch2) == 0) {
                       window.remove(ch2);                }                left++;            }            // check失败，则right继续向后，直到符合            right++;        }                return res;    }    // 当前窗口是否符合题目条件    public boolean check(Map
     
       window, Map
      
        chars) {
           for (char ch : chars.keySet()) {
               // window存在所有子串字符            if (!window.containsKey(ch) || (window.get(ch) < chars.get(ch))) {
                   return false;            }        }        return true;    }}
      
     
    
   

快慢指针

快慢指针，一般用于解决链表问题，快指针每次走n步或者提前走n步，而慢指针还是一步一步原地走

/** * Title：NC53-删除链表倒数第n个值,并返回头结点 * Description： 要求O(n) * @author WZQ * @version 1.0.0 * @date 2021/2/27 */public class NC53 {
       /**     * @param head ListNode类     * @param n int整型     * @return ListNode类     */    public ListNode removeNthFromEnd (ListNode head, int n) {
           if(head == null){
               return head;        }        // 双指针，快慢指针        // 采用两个指针，对前指针，使其先走出N步，随后两个指针同时前进，        // 当前指针到达链表尾部时，后指针到达倒数第N个节点的位置。        ListNode slow = head;        ListNode fast = head;        // 先走n步        for(int i = 0; i 

import java.util.List;/** * Title：NC4-寻找链表闭环 * Description： * @author WZQ * @version 1.0.0 * @date 2021/1/7 */public class NC4 {
       /**     * 思路1：hash map/set     * 开一个哈希表，标记访问过的节点，     * 如果重复访问了某一节点，说明有环。     * 需要额外O(n)的空间复杂度。     */    /**     * 思路2：快慢指针     * 用一快一慢指针，开始两个指针都指向链表头部。     * 慢指针每次向前走一步，快指针每次向前走两步。     * 如果有环，则两个指针最终一定会相遇。     * 这种方法无须额外的空间。     * @param head     * @return     */    public boolean hasCycle(ListNode head) {
           if (head == null || head.next == null){
               return false;        }        ListNode s = head;        ListNode q = head;        while (q != null && q.next != null){
               s = s.next;            q = q.next.next;            if (s == q){
                   return true;            }        }        return false;    }    //Definition for singly-linked list.    class ListNode {
           int val;        ListNode next;        ListNode(int x) {
               val = x;            next = null;        }    }}

链表闭环升级版，寻找环的入口节点

/** * Title：NC-3，链表的入口节点，环的入口节点 * Description：双指针 * * @author WZQ * @version 1.0.0 * @date 2021/3/5 */public class NC3 {
       /**     * 1）首先判断是否有环,有环时，返回相遇的节点，无环，返回null     * 2）有环的情况下， 求链表的入环节点     * fast再次从头出发，每次走一步，     * slow从相遇点出发，每次走一步，     * 再次相遇即为环入口点。     */    public ListNode detectCycle(ListNode head) {
           if (head == null || head.next == null){
               return null;        }        ListNode meetNode = meetingNode(head);        //说明无环        if (meetNode == null) {
               return null;        }        //fast再次从头出发，每次走一步，        //slow从相遇点出发，每次走一步，        ListNode fast = head;        ListNode slow = meetNode;        //再次相遇即为环入口点        while (slow != fast) {
               slow = slow.next;            fast = fast.next;        }        return slow;    }    //寻找相遇节点，如果无环，返回null    public ListNode meetingNode(ListNode head) {
           ListNode slow = head;        ListNode fast = head;        while (fast != null && fast.next != null) {
               // 快指针走2步            slow = slow.next;            fast = fast.next.next;            // 相遇点            if (slow == fast) {
                   return slow;            }        }        return null;    }    //节点    class ListNode {
           int val;        ListNode next;        ListNode(int x) {
               val = x;            next = null;        }    }}

转载地址：http://pviwi.baihongyu.com/