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

快慢指针的常见算法

快慢指针一般都初始化指向链表的头结点 head，前进时快指针 fast 在前，慢指针 slow 在后，巧妙解决一些链表中的问题。

判定链表中是否含有环

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

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

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

寻找链表的中点

我们还可以让快指针一次前进两步，慢指针一次前进一步，当快指针到达链表尽头时，慢指针就处于链表的中间位置。

寻找链表的倒数第k个元素

我们的思路还是使用快慢指针，让快指针先走 k 步，然后快慢指针开始同速前进。
这样当快指针走到链表末尾 null 时，慢指针所在的位置就是倒数第 k 个链表节点。

左右指针的常用算法

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

二分查找

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 搜索区间[0,nums.length-1]
    while(left <= right) {
        int mid = left + (right - left) / 2;//防止整型溢出
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 缩小搜索区间
        else if (nums[mid] > target)
            right = mid - 1; // 缩小搜索区间
    }
    return -1;
}

前提：nums数组有序。
重要：不要出现 else，而是把三种情况用 else if 写清楚，这样可以清楚地展现所有细节。

两数之和

给定一个有序整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

暴力解法

hash映射

遍历数组 nums，i 为当前下标，每个值都判断map中是否存在 target-nums[i] 的 key 值
如果存在则找到了两个值，如果不存在则将当前的 (nums[i],i) 存入map 中，继续遍历直到找到为止

双指针

类似二分查找，通过调节 left 和 right 可以调整 sum 的大小。

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) {
            left++; // 让 sum 大一点
        } else if (sum > target) {
            right--; // 让 sum 小一点
        }
    }
    return new int[]{-1, -1};
}

反转数组

void reverse(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        int temp = nums[left];// swap(nums[left], nums[right])
        nums[left] = nums[right];
        nums[right] = temp;
        left++; right--;
    }
}

反转字符串

滑动窗口算法

最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：
输入: S = “ADOBECODEBANC”, T = “ABC”
输出: “BANC”
说明：
如果 S 中不存这样的子串，则返回空字符串 “”。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

暴力解法

for (int i = 0; i < s.size(); i++)
    for (int j = i + 1; j < s.size(); j++)
        if s[i:j] 包含 t 的所有字母:
            更新答案

滑动窗口

思路如下：

我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。
我们先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。
重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。

show code

    public String minWindow(String s, String t) {
        char[] tArray = t.toCharArray();
        char[] sArray = s.toCharArray();
        Map<Character,Integer> need = new HashMap();
        for(int i=0;i<tArray.length;i++){
            int count = need.getOrDefault(tArray[i], 0);
            need.put(tArray[i], count + 1);
        }
        Map<Character,Integer> window=new HashMap();
        int left=0,right=0;
        int minLenth = Integer.MAX_VALUE;
        int valid=0;//匹配的字符数量
        int start=0;
        int size = need.keySet().size();
        while(right<sArray.length){
            char c = sArray[right];
            if (need.containsKey(c)) {// 进行窗口内数据的一系列更新
                int count = window.getOrDefault(c, 0);
                window.put(c, count + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }
            while(valid==size){
                if (right - left+1 < minLenth) {// 在这里更新最小覆盖子串
                    start = left;
                    minLenth = right - left+1;
                }
                char d = sArray[left];// d 是将移出窗口的字符
                left++;// 左移窗口
                // 进行窗口内数据的一系列更新
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d,window.get(d)-1);
                }
            }
            right++;//右指针右移
        }
        return minLenth==Integer.MAX_VALUE?"":s.substring(start,start+minLenth);
    }

字符串排列

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例1:
输入: s1 = “ab” s2 = “eidbaooo”
输出: True
解释: s2 包含 s1 的排列之一 (“ba”).

这种题目相当给你一个 S 和一个 T，请问你 S 中是否存在一个子串，包含 T 中所有字符且不包含其他字符？
这道题的解法和最小覆盖子串类似，只需要改变两个地方：
1、本题移动 left 缩小窗口的时机是窗口大小大于 t.size() 时，应为排列嘛，显然长度应该是一样的。
2、当发现 valid == need.size() 时，就说明窗口中就是一个合法的排列，所以立即返回 true。

找所有字母异位词

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：
字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。

示例:
输入:
s: “cbaebabacd” p: “abc”
输出:
[0, 6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的字母异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的字母异位词。

这个所谓的字母异位词，不就是排列吗。相当于，输入一个串 S，一个串 T，找到 S 中所有 T 的排列，返回它们的起始索引。和上题一样的！

最长无重复子串

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

这就是变简单了，连 need 和 valid 都不需要，而且更新窗口内数据也只需要简单的更新计数器 window 即可。
当 window[c] 值大于 1 时，说明窗口中存在重复字符，不符合条件，就该移动 left 缩小窗口了。