双指针：反向扫描和同向扫描

双指针的应用场景

双指针（又称为尺取法）是算法竞赛中常用的一个优化技巧，用来解决序列的区间问题。

我们一般用 i 和 j 分别扫描区间，i 和 j 有如下两种扫描方向

反向扫描：i 和 j 方向相反，i 从头到尾，j 从尾到头，在中间相会 同向扫描：i 和 j 方向相同，都从头到尾，速度不同，让 j 跑在 i 前面

把同向扫描的 i, j 指针称为‘快慢指针’，快慢指针可以用来解决链表是否有环，数组去重等，并且快慢指针在序列上产生了一个大小可变的滑动窗口，可以用解决滑动窗口相关的问题，比如寻找区间

把反向扫描的 i, j 指针称为‘左右指针’

反向扫描

判断是否为回文字符串

题目描述： 题目来源：BM88（牛客网）

public class Solution {

    public boolean judge(String str) {
        int start = 0;
        int end = str.length() - 1;
        boolean result = true;
        while (start <= end) {
            if (str.charAt(start) != str.charAt(end)) {
                result = false;
                break;
            }
            start++;
            end--;
        }
        return result;
    }
}

最长回文子串

题目描述： 题目来源：LeetCode 5

我们可以采用中心扩展法来找到最长回文子串，把字符串的每个字符或每2个相同的字符看作中心，然后扩展检查，判断它左右对称位置是否相同，若相同，则是回文串的一部分，直到对称位置不同为止

class Solution {

    int max = 1, finalStart = 0, finalEnd = 0;

    public String longestPalindrome(String s) {
        for (int i = 0; i < s.length(); i++) {
            // 单个字符看作中心，扩展检查
            judge(i - 1, i + 1, s);
            // 两个字符看作中心，扩展检查
            judge(i - 1, i, s);
        }
        return s.substring(finalStart, finalEnd + 1);
    }

    public int judge(int start, int end, String s) {
        while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
            if (end - start + 1 > max) {
                max = end - start + 1;
                finalStart = start;
                finalEnd = end;
            }
            start--;
            end++;
        }
        return max;
    }
}

同向扫描

判断链表是否有环

题目描述：判断给定的链表中是否有环。如果有环则返回true，否则返回false。

题目来源：BM6（牛客网）

public class Solution {

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

删除有序数组中的重复项

题目描述： 题目来源：LeetCode 26

public class Solution {

    public int removeDuplicates(int[] nums) {
        if (nums.length == 1) {
            return 1;
        }
        int slow = 1, fast = 1;
        while (fast < nums.length) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                slow++;
                fast++;
            } else {
                fast++;
            }
        }
        return slow;
    }
}

滑动窗口

滑动窗口主要逻辑就是从右侧增大窗口和从左侧缩小窗口

最长无重复子数组

题目描述： 题目来源：BM92（牛客网）

思路分析：依次以数组中的每个元素为起点，往后移动，直到遇到重复元素，然后计算子数组的长度求最值

public class Solution {

    public int maxLength(int[] arr) {
        int max = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            map.clear();
            int j = i;
            for (; j < arr.length; j++) {
                Integer num = map.getOrDefault(arr[j], 0);
                if (num != 0) {
                    break;
                }
                map.put(arr[j], 1);
            }
            max = Math.max(max, j - i);
        }
        return max;
    }
}

但上面的过程还可以简化一下，我们以下图为例演示一下上面的过程

1. 子数组以7开头，遍历到第2个5时，有重复元素了，子数组的开头为7，结尾为1，区间长度为5
2. 接着子数组以8开头，遍历到第2个5时，有重复元素了，子数组的开头为7，结尾为1，区间长度为4
3. 接着子数组以6开头，遍历到第2个5时，有重复元素了，子数组的开头为6，结尾为1，区间长度为3

仔细想一下其实2，3步是没有必要的，因为遇到第2个5的时候总会有重复元素的，而且因为开头往后延了，长度还缩小了。直接从第1个5后面的元素开始重新遍历即可。

public class Solution {
    
    public int maxLength(int[] arr) {
        int max = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0, j = 0; j < arr.length; j++) {
            Integer k = map.get(arr[j]);
            if (k != null) {
                // 防止开头回退的情况，比如当 i 指向数组倒数第二个元素，j 指向数组倒数第一个元素
                i = Math.max(i, k + 1);
            }
            map.put(arr[j], j);
            max = Math.max(max, j - i + 1);
        }
        return max;
    }
}

找到字符串中所有字母异位词

题目描述： 题目来源：LeetCode 438

思路分析：形成固定大小的窗口后，窗口依次向前移动一个元素，然后判断窗口内的元素是否满足要求

class Solution {

    Map<Character, Integer> allMap = new HashMap<>();
    Map<Character, Integer> subMap = new HashMap<>();
    
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < p.length(); i++) {
            subMap.put(p.charAt(i), subMap.getOrDefault(p.charAt(i), 0) + 1);
        }
        for (int i = 0, j = 0; j < s.length(); j++) {
            allMap.put(s.charAt(j), allMap.getOrDefault(s.charAt(j), 0) + 1);
            if (j >= p.length() - 1) {
                if (check()) {
                    result.add(i);
                }
                allMap.put(s.charAt(i), allMap.get(s.charAt(i)) - 1);
                i++;
            }
        }
        return result;
    }

    public boolean check() {
        for (Map.Entry<Character, Integer> entry : subMap.entrySet()) {
            char key = entry.getKey();
            int subCount = entry.getValue();
            if (allMap.getOrDefault(key, 0) < subCount) {
                return false;
            }
        }
        return true;
    }
}

最小覆盖子串

题目描述： 题目来源：LeetCode 76

思路分析：

1. 慢指针为字符串的开头，快指针一直向前移动，直到子串能覆盖 t，然后慢指针再向前移动，直到多移动一步不能覆盖 t 为止，求出长度进行比较。
2. 然后将慢指针多移动一步作为起点，快指针一直向前移动，重复1的过程

class Solution {

    Map<Character, Integer> allMap = new HashMap<>();
    Map<Character, Integer> subMap = new HashMap<>();

    public String minWindow(String s, String t) {
        String minStr = "";
        for (int i = 0; i < t.length(); i++) {
            subMap.put(t.charAt(i), subMap.getOrDefault(t.charAt(i), 0) + 1);
        }
        for (int i = 0, j = 0; j < s.length(); j++) {
            allMap.put(s.charAt(j), allMap.getOrDefault(s.charAt(j), 0) + 1);
            while (check() && i <= j) {
                if (minStr.isEmpty() || minStr.length() > j - i + 1) {
                    minStr = s.substring(i, j + 1);
                }
                allMap.put(s.charAt(i), allMap.get(s.charAt(i)) - 1);
                i++;
            }
        }
        return minStr;
    }

    public boolean check() {
        for (Map.Entry<Character, Integer> entry : subMap.entrySet()) {
            char key = entry.getKey();
            int subCount = entry.getValue();
            Integer allCount = allMap.getOrDefault(key, 0);
            if (allCount < subCount) {
                return false;
            }
        }
        return true;
    }
}