双指针

双指针顾名思义是有两个变量，分别指向不同的位置。

双指针可以分为：

• 同向指针（快慢指针，滑动窗口）
• 反向指针（二分搜索）

同向指针

同向指针是两个指针的移动方向是相同的。

快慢指针

快慢指针主要用于解决判断链表中环的问题。

判断链表中是否有环

如果链表中没有环，一个指针从头遍历，最终一定会走到null的。但如果链表中有环，则一个指针永远也走不到null，代码会陷入到死循环。

解法：为了验证链表中有环，使用快慢指针，一个指针走的快，另一个指针走的慢。如果链表中没有环，快指针会走到null；如果链表中有环，快指针会与慢指针相遇。

链表中有环，快慢指针一定会相遇

证明：假设环的长度为m，慢指针的在环中的位置为0,快指针在环中的位置为b，假设慢指针经过k步之后相遇。

此时慢指针的位置为 $(0+k)\%m$ ，快指针的位置为 $(b + 2k)\%m$。若要相遇则$(k)\%m = (b + 2k)\%m$ 可得出 $ (k = -b)\%m$ 说明k一定是存在的。

/**
 * check link has loop or not
 * @param link
 * @return hasLoop Boolean
 */
public boolean hasLoopInLink(Node head) {
    Node fast = head;
    Node slow = head;
    while(fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
        if(slow == fast){
            return true;
        }
    }
    return false;
}

找出链表中环的起点

已知链表中有环，返回环的起点。

解法：当快慢指针相遇后，选择其中一个指针指向起始位置，然后再一起以每次一步的速度前进，两者再次相遇的地点即为环的起点。

链表中环的起点，是当快慢指针相遇后，选择其中一个指针指向起始位置，然后再一起以每次一步的速度前进，两者再次相遇的地点。

证明：当快慢指针第一次相遇的时候，快指针一定是比慢指针多走环长度(m)的整数倍，假定此时慢指针走了n步，那么快指针就走了2n步。假设链表的起点与环的起点相距为k步，对于慢指针：环的起点到快慢指针第一次相遇的点距离为$(n-k)\mod m$步；对于快指针：$2n = x \times m + k + n - k = x\times m + n => x \times m = n$ 其中$x\in[1,2,…]$

此时将其中一个指针指向链表的起点，再让两个指针同时以一步的速度前进，明显第一个指针走k步后到达了环的起点；第二个指针从第一次相遇的点到环的起点距离是$m-((n-k)\mod m)$，将上述m与n的关系代入，得出$m-((x \times m - k)\mod m) = m - ((-k)\mod m) = m - (m - (k \mod m)) = k\mod m$，所以第二个指针向前走k步，也一定会走到环的起点；两个指针再次相遇的位置即为环的起点。

/**
 * find loop start point 
 * @param head
 * @return loop start point
 */
public Node loopStartPoint(Node head){
    Node fast = head;
    Node slow = head;
    while(fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
        if(slow == fast){
            slow = head;
            while(slow != fast){
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    return null;
}

找出无环链表的中点

一种简单暴力的方法是首先遍历一遍整个链表，记录链表的长度$n$，然后再次遍历链表到$\frac{n}{2}$的位置即为链表的中点。但通过双指针可以一次遍历完成任务。

解法：快指针、慢指针同时指向链表起点，快指针每次走两步，慢指针每次走一步，等到快指针到达链表尾部时，慢指针正处于链表的中点。

注：当链表长度为奇数时，slow正好停在链表中点的位置；当链表长度时偶数时，slow最终的位置是中点偏右。

/**
 * find mid position of linked-list
 * 
 * @param head
 * @return
 */
public Node findMidPoint(Node head) {
    Node fast = head;
    Node slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

找出链表倒数第k个元素

解法：快指针、慢指针同时指向链表的起点，让快指针先走k步，然后慢指针和快指针同时移动，但快指针走到链表尾部，慢指针的位置即为链表倒数第k个元素。

/**
 * find the last kth element of linked-list
 * 
 * @param head
 * @param k
 * @return
 */
public Node findLastKthElement(Node head, int k) {
    Node fast = head;
    Node slow = head;
    while (k > 0 && fast != null) {
        fast = fast.next;
        k--;
    }
    if (k > 0)
        return null;
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

滑动窗口

滑动窗口保持两个指针（前指针和后指针），两个指针之间的范围为当前有效范围，不断根据条件滑动两个指针，直到最后输出满足条件的有效范围（前后两个指针）。滑动窗口主要用于解决子串问题。

滑动窗口一般分为两种类型：

• 固定大小窗口：寻找或处理长度固定的连续子数组，例如计算所有长度为 k 的子数组的最大和。
• 可变大小窗口：寻找满足特定条件的最长或最短的连续子串/子数组，例如寻找不包含重复字符的最长子串。

下面给出滑动窗口（可变大小窗口）的主要框架：

void slidingWindow(String a, String b){
    int left=0, right=0;
    while(right < a.size()){
        // 将a.charAt(right)加入到窗口字符
        // 对窗口字符进行一系列更新
        right++;
        while(窗口是否需要收缩){
            // [left, right)子串 满足条件
            // 将 a.charAt(left) 移除窗口字符
            // 对窗口字符进行一系列更新
            left++;
        }
    }
}

下面列出一些列使用滑动窗口的题目类型

可变大小窗口

无重复字符的最长子串

使用滑动窗口向右移动，若右侧元素不与窗口中其他元素重复，则将右侧元素添加到滑动窗口；否则缩小滑动窗口左侧直到右侧元素不重复。用Set来记录滑动窗口中包含的字符。

public int lengthOfLongestSubstring(String s) {
    HashSet<Character> con = new HashSet<>();
    int maxlength = 0;
    int start = 0, end = 0;
    while (end < s.length()) {
        if (con.contains(s.charAt(end))) {
            con.remove(s.charAt(start));
            start++;
        } else {
            con.add(s.charAt(end));
            end++;
            maxlength = Math.max(maxlength, end - start);
        }
    }
    return maxlength;
}

最小覆盖子串

给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""。测试用例保证答案唯一。

看到这个问题，最直接的想法是暴力搜索，遍历字符串s中所有可能的子串并判断其是否符合 包含 t 中的每一个字符 的条件，这个复杂度至少是$O(N^2)$级别的。但使用贪心算法+双指针可以在$O(N)$级别内解决。

解法：

1. 创建双指针left和right，left代表子串的起点，right代表子串的终点，初始时两者都在字符串s的起点
2. right指针向前移动，增加包含字符子串的字符，直到该子串包含字符串t的所有字符，停止移动right
3. left指针开始向前移动，缩小子串的长度，直到去掉某些字符让子串不包含字符串t的所有字符，停止移动left；每次移动left之前需要判断满足条件的字符串是不是更小的，保存更小的结果
4. 重复执行步骤2和步骤3，直到right到达字符串s的尾部

这个解法实际上是贪心算法，先移动right尽可能的包含新的字符，用来满足包含字符串t的所有字符的条件；再移动left用来收缩子串，尽可能的在满足条件的情况下缩短子串的长度。

对于如何判断子串中是否包含字符串t的所有字符，使用哈希表来实现。一个哈希表(charMap:Map)包含字符串t的所有字符以及对应的数量。satisfy为charMap的大小，表示需要满足的字符个数，当charMap中某个字符数量从0到1表示滑动窗口中需要一个该字符，safisfy加一；当charMap中某个字符从1到0表示该字符在滑动窗口中已经满足，safisfy减一。当satisfy为0时，表示所有的字符都已经满足。

public String minWindow(String s, String t) {
    HashMap<Character, Integer> charMap = new HashMap<>();
    int resL = 0, resR = Integer.MAX_VALUE;

    for (Character tc : t.toCharArray()) {
        charMap.put(tc, charMap.getOrDefault(tc, 0) + 1);
    }
    int satisfy = charMap.size();
    int start = 0, end = 0;
    while (end < s.length()) {
        char charEnd = s.charAt(end);
        if (charMap.containsKey(charEnd)) {
            charMap.put(charEnd, charMap.get(charEnd) - 1);
            if (charMap.get(charEnd) == 0) {
                satisfy--;
            }
        }
        end++;

        while (satisfy == 0) {
            // result
            if (resR - resL > end - start) {
                resL = start;
                resR = end;
            }

            char charStart = s.charAt(start);
            if (charMap.containsKey(charStart)) {
                charMap.put(charStart, charMap.get(charStart) + 1);
                if (charMap.get(charStart) == 1) {
                    satisfy++;
                }
            }
            start++;
        }
    }

    return resR != Integer.MAX_VALUE ? s.substring(resL, resR) : "";
}

长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target。找出该数组中满足其总和大于等于 target 的长度最小的 子数组 $[nums_l, nums_{l+1}, …, nums_{r-1}, nums_r]$ ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

public int minSubArrayLen(int target, int[] nums) {
    int minLength = Integer.MAX_VALUE;
    int curSum = 0;
    int start=0,end=0;
    while(end < nums.length){
        curSum += nums[end];
        end++;

        while(curSum >= target){
            minLength = Math.min(minLength, end - start);
            curSum -= nums[start];
            start++;
        }
    }
    return minLength != Integer.MAX_VALUE ? minLength : 0;
}

替换后的最长重复字符

注：此题思路不难，但实现不易，应该是Hard的

假设替换后的重复字符子串的长度为 n，那么其中必然包含 k 个其他字符和 $n-k$ 个相同的字符（且该字符重复次数为最多）。如此搜索条件就变为了 滑动窗口中除了重复次数最多的字符外其他字符数量只能为 k 个。

难点是：如何动态记录在窗口滑动过程中，重复次数最多的字符及其重复次数。第一想到是用Map动态维护最大堆，比如map.put后会自动调整最大堆，通过map.peek取出最大的[key, value]。但目前Java没有提供这样的数据结构。如果每次都扫一遍map，则整体的时间复杂度为$O(N^2)$。

具体的代码：

public int characterReplacement(String s, int k) {
    HashMap<Character, Integer> recordMap = new HashMap<>();    
    int start = 0, end = 0;
    while (end < s.length()) {
        char charEnd = s.charAt(end++);
        recordMap.put(charEnd, recordMap.getOrDefault(charEnd, 0) + 1);
        
        while (end - start > 取出recordMap中最大值 + k) {
            char charStart = s.charAt(start++);
            recordMap.put(charStart, recordMap.get(charStart) - 1);
        }
    }
    return s.length() - start;
}

其中 取出recordMap中最大值 需要遍历 map 中所有数据，时间复杂度为$O(N)$，而每次start移动都要遍历map，故总时间复杂度为$O(N^2)$，明显超时。

要优化时间复杂度，因为寻找的是最长重复字符，所以当找到一个满足条件的子串后只需要寻找比该子串长度长的子串即可。一开始让end先向右移动，当end - start > maxLength + k条件满足后，即当前窗口不合法，将start+1，让子串长度继续保持在maxLength + k或更大（因为end+1后导致不满足，end不能再增加了，此时将left+1,给end移动的可能性，即当条件不满足后 end 与 start 是同时向后移动的，维持滑动窗口的长度不变。

public int characterReplacement(String s, int k) {
    HashMap<Character, Integer> recordMap = new HashMap<>();
    int maxLength = 0;
    int start = 0, end = 0;
    while (end < s.length()) {
        char charEnd = s.charAt(end++);
        recordMap.put(charEnd, recordMap.getOrDefault(charEnd, 0) + 1);
        maxLength = Math.max(maxLength, recordMap.get(charEnd));

        if (end - start > maxLength + k) {
            char charStart = s.charAt(start++);
            recordMap.put(charStart, recordMap.get(charStart) - 1);
        }
    }
    return s.length() - start;
}

固定窗口大小

字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的 排列。如果是，返回 true ；否则，返回 false 。换句话说，s1 的排列之一是 s2 的 子串 。

借用 最小覆盖子串 的模板，本题的区别是要保证s2的子串就是s1字符串的一种组合，而最小覆盖子串中只需要保证子串中包含s1字符串的所有字符即可，子串中也可以包含其他字符。

整个步骤与最小覆盖子串是一样的，不同点在于满足子串包含s1所有字符后，要判断子串的长度与字符串s1的长度是否相同，若相同即为s2的子串是s1字符串的一种组合。

/*
 * @lc app=leetcode.cn id=567 lang=java
 *
 * [567] 字符串的排列
 */

// @lc code=start

import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for (Character chr : s1.toCharArray()) {
            need.put(chr, need.getOrDefault(chr, 0) + 1);
        }
        int left = 0, right = 0;
        int satisfy = 0;
        while (right < s2.length()) {
            Character rchr = s2.charAt(right);
            right++;
            if (need.containsKey(rchr)) {
                window.put(rchr, window.getOrDefault(rchr, 0) + 1);
                if (need.get(rchr).equals(window.get(rchr))) {
                    satisfy++;
                }
            }

            while (satisfy == need.size()) {
                if ((right - left) == s1.length()) {
                    return true;
                }
                Character lchr = s2.charAt(left);
                left++;
                if (need.containsKey(lchr)) {
                    if (need.get(lchr).equals(window.get(lchr))) {
                        satisfy--;
                    }
                    window.put(lchr, window.get(lchr) - 1);
                }
            }
        }
        return false;
    }
}
// @lc code=end

但是该题目只需要判断一个固定长度的窗口，不需要移动完right再去移动left。

1. 首先移动right向前移动s1的长度，将字符放入到滑动窗口
2. 对满足s1长度滑动窗口的子串进行判断，是否是s2字符串的排列
3. 然后同步移动left和right，始终维持s1的长度的滑动窗口，每次都进行步骤2的判断

public boolean checkInclusion(String s1, String s2) {
    HashMap<Character, Integer> needMap = new HashMap<>();
    for (char cs1 : s1.toCharArray()) {
        needMap.put(cs1, needMap.getOrDefault(cs1, 0) + 1);
    }
    int satisfy = needMap.size();
    int start = 0, end = 0;
    while (end < s2.length()) {
        char curEnd = s2.charAt(end);
        if (needMap.containsKey(curEnd)) {
            needMap.put(curEnd, needMap.get(curEnd) - 1);
            if (needMap.get(curEnd) == 0) {
                satisfy--;
            }
        }
        end++;

        if (end - start < s1.length())
            continue;

        if (satisfy == 0) {
            return true;
        }

        char curStart = s2.charAt(start);
        if (needMap.containsKey(curStart)) {
            needMap.put(curStart, needMap.get(curStart) + 1);
            if (needMap.get(curStart) == 1) {
                satisfy++;
            }
        }
        start++;
    }
    return false;
}

滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。

最简单的思路是对每一个滑动窗口遍历一次，找出最大值。但复杂度为$O(nk)$即$O(n^2)$，其数据量$n=10^5$会超时。但数据量超过$10^4$要将时间复杂度降低到$O(nlog(n))$以下。所以寻找最大值不能用暴力搜索。

动态寻找极值的最佳数据结构是最大（小）堆

• 最大堆和最小堆构建的时间复杂度为 逐个插入为$O(nlogn)$，Floyd 建堆为$O(n)$

因为每次向右移动滑动窗口是添加一个右侧元素，删除一个左侧元素。所以可以动态维护一个最大堆，取出每次的最大值。但从最大堆中删除元素的复杂度为$O(n)$，插入元素的复杂度为$O(logn)$，所以可以插入右侧元素，但不能删除左侧元素。否则单次操作的复杂度就是$O(n)$了（要控制在$O(logn)$以内）。

这样导致滑动窗口左侧已经出去的元素，仍然留在最大堆中，所以需要额外的存储来区别哪些元素已经从左侧排除了。

为了记录哪些元素从左侧排除了，有两种方案：一为通过计数Set记录当前滑动窗口中哪些元素有效，二为直接在最大堆中记录元素的下标判断元素是否在滑动窗口左侧。

解法一：使用计数Set

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        ArrayList<Integer> result = new ArrayList<>(nums.length - k + 1);
        CountingSet<Integer> vaildChar = new CountingSet<>(k);
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, Comparator.reverseOrder());
        int start = 0, end = 0;
        while (end < nums.length) {
            // move right
            maxHeap.offer(nums[end]);
            vaildChar.add(nums[end]);
            end++;
            if (end - start < k) {
                continue;
            }

            // end - start = k
            int cur = maxHeap.peek();
            while (!vaildChar.contains(cur)) {
                maxHeap.poll();
                cur = maxHeap.peek();
            }
            result.add(cur);

            // move left
            vaildChar.remove(nums[start]);
            start++;
        }
        return result.stream().mapToInt(Integer::intValue).toArray();
    }


    class CountingSet<E> {
        private Map<E, Integer> map;

        public CountingSet(int size) {
            map = new HashMap<>(size);
        }

        // 添加元素，计数 +1
        public void add(E element) {
            map.put(element, map.getOrDefault(element, 0) + 1);
        }

        // 删除一次该元素（如果计数 > 0）
        public boolean remove(E element) {
            Integer count = map.get(element);
            if (count == null || count <= 0) {
                return false; // 不存在或已删完
            }
            if (count == 1) {
                map.remove(element);
            } else {
                map.put(element, count - 1);
            }
            return true;
        }

        public boolean contains(E element) {
            return map.containsKey(element);
        }

        // 获取元素当前计数
        public int getCount(E element) {
            return map.getOrDefault(element, 0);
        }

        // 完全移除所有该元素
        public void removeAll(E element) {
            map.remove(element);
        }
    }
}

解法二：直接在最大堆中记录元素的下标

class Pair implements Comparable<Pair> {
    int value;
    int index;

    public Pair(int value, int index) {
        this.value = value;
        this.index = index;
    }
    // 保证降序排列
    public int compareTo(Pair other) {
        return this.value != other.value ? other.value - this.value : other.index - this.index;
    }
}

public int[] maxSlidingWindow(int[] nums, int k) {
    ArrayList<Integer> result = new ArrayList<>();
    PriorityQueue<Pair> maxHeap = new PriorityQueue<>(k);
    int start = 0, end = 0;
    while (end < nums.length) {
        maxHeap.add(new Pair(nums[end], end));
        end++;
        if (end - start < k) {
            continue;
        }
        Pair cur = maxHeap.peek();
        while (cur.index < start) {
            maxHeap.poll();
            cur = maxHeap.peek();
        }
        result.add(cur.value);
        start++;
    }
    return result.stream().mapToInt(Integer::intValue).toArray();
}

解决滑动窗口的最值问题最好的方法是单调队列。单调队列即元素单调递增或单调递减。寻找滑动窗口中的最大值需要将滑动窗口右侧元素添加到队列尾部并将队列中所有小于该值的元素都弹出；然后将左侧元素从队列头部删除。每次拿出队列头部元素为滑动窗口的最大值。

解法三：单调队列

public int[] maxSlidingWindow(int[] nums, int k) {
    ArrayList<Integer> result = new ArrayList<>();
    Deque<Integer> singleQueue = new ArrayDeque<>();
    int start = 0, end = 0;
    while (end < nums.length) {
        while (!singleQueue.isEmpty() && nums[singleQueue.peekLast()] <= nums[end]) {
            singleQueue.pollLast();
        }
        singleQueue.offerLast(end);

        end++;
        if (end - start < k) {
            continue;
        }

        result.add(nums[singleQueue.peekFirst()]);

        start++;
        while (!singleQueue.isEmpty() && singleQueue.peekFirst() < start) {
            singleQueue.pollFirst();
        }
    }
    return result.stream().mapToInt(Integer::intValue).toArray();
}

子数组最大平均数 I

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。

记录每个窗口中所有元素的总和，窗口向右滑动时，将右侧元素加入到总和，将左侧元素减出。依次比较取出最大值。

此题目比 滑动窗口最大值 简单是因为在滑动窗口时，只需要加入右侧元素，减左侧元素即可得到区间和，复杂度为$O(1)$；而后者题目需要找出区间的最大值，常规复杂度为$O(n)$，会导致总的复杂度为$O(n^2)$，需要将单次窗口的复杂度降为$O(logn)$。

public int lengthOfLongestSubstring(String s) {
    HashSet<Character> con = new HashSet<>();
    int maxlength = 0;
    int start = 0, end = 0;
    while (end < s.length()) {
        if (con.contains(s.charAt(end))) {
            con.remove(s.charAt(start));
            start++;
        } else {
            con.add(s.charAt(end));
            end++;
            maxlength = Math.max(maxlength, end - start);
        }
    }
    return maxlength;
}

反向指针

反向指针是两个指针的移动方向是相反（相向）的。

二分搜索

二分搜索主要用于寻找一个数，寻找左侧边界，寻找右侧边界。

寻找一个特定的数

针对一个有序的数组num，快速寻找出该数组的某个数target。

步骤：

1. 左指针指向数组开始，右指针指向数组结尾
2. 计算数组的中间位置mid
3. 若目标值target大于中间值num[mid]，则说明目标值在右侧区间，让left=mid+1；若目标值target小于中间值num[mid]，则说明目标值在左侧区间，让right=mid-1;若目标值target等于中间值num[mid]，则找到目标值，直接返回。
4. 更新数组区间[left,right]，跳转到第二步继续执行。

/**
 * binary search for int[]
 * 
 * @param num
 * @param target
 * @return
 */
public int binarySearch(int[] num, int target) {
    int left = 0, right = num.length - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (num[mid] < target) {
            left = mid + 1;
        } else if (num[mid] > target) {
            right = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

/**
 * binary search for any type array
 * 
 * @param <T>
 * @param num
 * @param target
 * @return
 */
public <T extends Comparable<T>> int binarySearch(List<T> num, T target) {
    int left = 0, right = num.size() - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        int cmp = num.get(mid).compareTo(target);
        if (cmp < 0) {
            left = mid + 1;
        } else if (cmp > 0) {
            right = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

二分算法有两种常用的实现，一类是左闭右开区间，一类是全闭区间。本文中选用全闭区间的实现代码。

针对全闭区间:

• 左指针指向数组的开始即num[0],又指针指向数组的结尾即num[len-1]，区间为[0,len-1]
• 结束条件为left > right即在while中的判断条件是while(left <= right)
• 判断区间后，缩小区间时；当缩小到左区间，right=mid-1；当缩小到右区间，left=mid+1

---

寻找特定值的二分搜索是找到数组的任意一个目标值，对于存在多个特定值的数组，不能一次性找到左右侧边界。（当然可以通过找到一个目标值然后向左向右遍历来找到边界，但这样复杂度就退化为$O(N)$了，二分的复杂度为$O(log(N))$。）

寻找左侧边界的二分搜索

主体结构与寻找特定值的二分搜索一样，不同点在于找到特定值后不直接返回，让右侧边界继续向左侧靠拢，直到超出最左侧的边界，当left = right + 1时返回left（此时right已经超出搜索区间）。

/**
 * find left boundry using binary search
 * 
 * @param <T>
 * @param num
 * @param target
 * @return
 */
public <T extends Comparable<T>> int binarySearhLeftBoundry(List<T> num, T target) {
    int left = 0, right = num.size() - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        int cmp = num.get(mid).compareTo(target);
        if (cmp < 0) {
            left = mid + 1;
        } else if (cmp > 0) {
            right = mid - 1;
        } else {
            right = mid - 1;
        }
    }
    if (left >= num.size() || num.get(left) != target) {
        return -1;
    }
    return left;
}

寻找右侧边界的二分搜索

与寻找左侧一样，当找到特定值后不立即返回，让左侧边界继续向右侧靠拢，直到超出右侧边界，当left = right + 1时返回right（此时left已经超出搜索区间）。

/**
 * find right boundry using binary tree
 * 
 * @param <T>
 * @param num
 * @param target
 * @return
 */
public <T extends Comparable<T>> int binarySearchRightBoundry(List<T> num, T target) {
    int left = 0, right = num.size() - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        int cmp = num.get(mid).compareTo(target);
        if (cmp < 0) {
            left = mid + 1;
        } else if (cmp > 0) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    if (right < 0 || num.get(right) != target) {
        return -1;
    }
    return right;
}

题目

在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

题目需要寻找左侧边界和右侧边界，通过两次二分搜索，分别寻找左侧和右侧边界，时间复杂度仍为$O(logn)$

public int[] searchRange(int[] nums, int target) {
    return new int[] {searchLeft(nums, target), searchRight(nums, target)};
}

public int searchLeft(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left >> 1);
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            right = mid - 1;
        }
    }
    if (left >= nums.length || nums[left] != target) {
        return -1;
    }
    return left;
}

public int searchRight(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left >> 1);
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    if (right < 0 || nums[right] != target) {
        return -1;
    }
    return right;
}

寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。你可以假设 nums[-1] = nums[n] = -∞ 。你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

• 对于所有有效的 i 都有 nums[i] != nums[i + 1]

本题最重要的一点是nums[-1] = nums[n] = -∞，说明数组中存在至少一个峰值，只要按照递增方向走就一定能找到一个峰值。因为按照递增走无论是在数组中遇到递减还是走到结尾都是一个峰值。

如果随机找一个元素开始按照递增搜索，最差的时间复杂度依然是$O(n)$。

因为 nums[i] != nums[i + 1]所以对一任何有效的i，会出现

• nums[i-1] < nums[i] > nums[i+1]：找到峰值
• nums[i-1] > nums[i] > nums[i+1]：向左侧寻找峰值
• nums[i-1] < nums[i] < nums[i+1]：向右侧寻找峰值
• nums[i-1] > nums[i] < nums[i+1]：向左侧 右侧寻找峰值均可

所以统一向递增的方向搜索，即对于有效的i，nums[i] < nums[i+1]向右侧搜索，nums[i] > nums[i+1]向左侧搜索。当nums[i] < nums[i+1]向右侧搜索，则[left, i]区间可被忽略，故只需在[i+1, right]区间内搜索。在[i+1, right]区间内选择一个有效的j，继续上面的判断。

本题之所以能用二分搜索，是因为保证了一定有峰值，而且只需要一直按递增方向寻找就一定能找到。

本题不能直接套用二分的模板，二分模板是寻找某个特定值，而本题是比较第i个元素和第i+1各元素。仍然使用闭区间[0, nums.length-1]，寻找中点mid 判断nums[mid] 和 nums[mid + 1]的大小，因为[left, right]的中点是$\frac{left + right}{2}$去掉小数点。故中点是向left靠近的，当left=right,mid+1就超过了right,不合法，故while的终止条件为left<right。当nums[mid] > nums[mid + 1]向左侧搜索，而mid仍可能为峰值，故收缩区间到[left, mid]；当nums[mid] < nums[mid + 1]向右侧搜索，但mid+1的元素是大于mid的，mid不可能是峰值了，故收缩区间到[mid+1, right]。但left=right时，有两者可能：1.$left’ + 1 = left = right$，说明 nums[left’] < nums[right]，搜索结束right为峰值元素。2.$left = right = right’ - 1$，在区间[left, right’]中，因为相差1,所以mid=left,收缩时，right=mid=left，说明 nums[left] > nums[right’]，搜索结束left为峰值元素。（其中包含两端默认的条件，nums[-1] < nums[0], nums[nums.length-1] > nums[nums.length])

public int findPeakElement(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = left + (right - left >> 1);
        if (nums[mid] > nums[mid + 1]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
• 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

对于旋转数组有以下三种情况：

1. 没有旋转 nums[left] < nums[mid] < nums[right]
2. 大量旋转 nums[right] < nums[left] < nums[mid]
3. 少量旋转 nums[mid] < nums[right] < nums[left]

因为原数组是升序排列，所以旋转后，nums[left] > nums[right]。

当 nums[mid] < nums[right]，最小值在mid的左侧（包含mid）；当 nums[mid] > nums[right]，最小值在mid的右侧（不包含mid）。当left == right 时找到最小值。

public int findMin(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = left + (right - left >> 1);
        if (nums[mid] < nums[right]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return nums[left];
}

搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 向左旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 下标 3 上向左旋转后可能变为 [4,5,6,7,0,1,2] 。给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

本题与上面寻找旋转排序数组中的最小值的区别是从寻找最小值变为特定值。上面题目是将 nums[mid]与 nums[left] 和 nums[right]比较，缩小区间寻找最小值。本题需要比较 nums[target] 在 [left, mid]区间和 [mid, right]区间的关系。分以下情况：

• 旋转数组在 [left, mid] 上是单调递增的：
  • nums[target]落在[nums[left], nums[right]]区间内，缩小区间到[left, mid]
  • nums[target]不落在[nums[left], nums[right]]区间内，缩小区间到[mid+1, right]
• 旋转数组在 [mid, right] 上是单调递增的
  • nums[target]落在[nums[mid], nums[right]]区间内，缩小区间到[mid, right]
  • nums[target]不落在[nums[mid], nums[right]]区间内，缩小区间到[left, mid-1]

public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = left + (right - left >> 1);
        if (nums[mid] >= nums[left]) {
            if (nums[left] <= target && nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        } else {
            if (nums[mid] <= target && nums[right] >= target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
    }
    return nums[left] == target ? left : -1;
}

山脉数组的峰顶索引

给定一个长度为 n 的整数 山脉 数组 arr ，其中的值递增到一个 峰值元素 然后递减。返回峰值元素的下标。你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。

本题比寻找峰值还好理解，保证了只有一个峰值。思路是一致的，按照递增的方向收缩。

public int peakIndexInMountainArray(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int mid = left + (right - left >> 1);
        if (arr[mid] <= arr[mid + 1]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

搜索二维矩阵

很简单的二分，使用两次二分搜索，第一次找到目标值target所在的行，第二次在所在行中寻找目标值。注意边界条件即可。

public boolean searchMatrix(int[][] matrix, int target) {
    int index = searchIndexFirst(matrix, target);
    return searchIndexSecond(matrix, target, index);
}

public int searchIndexFirst(int[][] matrix, int target) {
    int left = 0, right = matrix.length - 1;
    while (left <= right) {
        int mid = left + (right - left >> 1);
        if (matrix[mid][0] < target) {
            left = mid + 1;
        } else if (matrix[mid][0] > target) {
            right = mid - 1;
        } else {
            return mid;
        }
    }
    return right < 0 ? 0 : right;
}

public boolean searchIndexSecond(int[][] matrix, int target, int index) {
    int left = 0, right = matrix[index].length - 1;
    while (left <= right) {
        int mid = left + (right - left >> 1);
        if (matrix[index][mid] < target) {
            left = mid + 1;
        } else if (matrix[index][mid] > target) {
            right = mid - 1;
        } else {
            return true;
        }
    }
    return false;
}

寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

本题最直观的解法是双指针共同向右走 $\frac{m+n}{2}$ ，时间复杂度为$(O(m+n))$。为了将时间复杂度降为$O(log(m+n))$，需要引入二分搜索。如何进行二分就成了解决此题的关键。

为了寻找中位数，需要将两个数组分成元素数量相同的左右两部分，左侧部分由nums1和nums2的部分左侧元素组成，右侧部分由nums1和nums2的部分右侧元素组成。所以需要在nums1和nums2中各自划一个分界线，将各自分为左侧部分和右侧部分。如nums1=[1,2,3,4,5],nums2=[2,3,4,5,6]，可以设定各自的分界线为nums1=[1,2

3,4,5],nums2=[2,3,4

5,6]，这样nums1Left=[1,2],nums2Left=[2,3,4],则左侧部分为[1,2,2,3,4]，右侧部分为[3,4,5,5,6]。

中位数的位置是在 $\frac{m + n}{2}$ (当m+n为奇数) 或 $\frac{m+n}{2} , \frac{m+n}{2} + 1$ (当m+n为偶数)，那么包含至少一个中位数（包含$\frac{m+n}{2}$）的左侧区间的元素数量是 $\frac{m+n+1}{2}$。

本题可以选择对 nums1（长度短的） 的分界线进行二分，二分的值即为nums1分界线左侧元素数量，左侧元素数量可以为0,为1,最多为m,所以需要二分的分界线左侧元素数量的范围是[0,m]全闭区间。

当nums1的分界线为定值 $i$ 后，nums2的分界线也确定为$\frac{m+n+1}{2} - i$，因为整体左侧的元素数量需要固定为$\frac{m+n+1}{2}$才是中位数。对于每个 $i$ , 判断当前分界线能否满足中位数的条件，条件为 左侧部分的最大值小于右侧部分的最小值。所以需要满足

• nums1LeftMax < nums1RightMin：自动满足
• nums1LeftMax < nums2RightMin：需要判断，如不满足，说明nums1分界线的选择偏大了，需要缩小i，即[i,right]的区间无效了。执行right=i-1

• nums2LeftMax < nums2RightMin：需要判断，如不满足，说明nums1分界线的选择偏小了，导致nums2的分界线偏大了。需要扩大i，即[left, i]的区间无效了。执行left = i + 1

• nums2LeftMax < nums2RightMin：自动满足

当上述所有条件满足后，

• 当 m+n 为奇数时，返回左侧部分的最大值即为中位数（因为左侧大小为$\frac{m+n+1}{2}$，至少包含一个中位数，包含$\frac{m+n}{2}$）
• 当 m+n 为偶数时，返回左侧部分的最大值和右侧部分的最小值的平均数

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    if (nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1);
    }
    int m = nums1.length, n = nums2.length;
    int left = 0, right = m;
    int totaLeft = (m + n + 1) / 2;
    while (left <= right) {
        int i = left + (right - left >> 1);
        int j = totaLeft - i;

        int num1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int num2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int num1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
        int num2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];

        if (num1LeftMax <= num2RightMin && num2LeftMax <= num1RightMin) {
            if ((m + n) % 2 == 1) {
                return (double) Math.max(num1LeftMax, num2LeftMax);
            } else {
                return (double) (Math.max(num1LeftMax, num2LeftMax)
                        + Math.min(num1RightMin, num2RightMin)) / 2;
            }
        } else if (num1LeftMax > num2RightMin) {
            right = i - 1;
        } else {
            left = i + 1;
        }
    }
    return 0.0;
}

咒语和药水的成功对数

给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等于 success ，那么它们视为一对 成功 的组合。

请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。

时间复杂度要求：$O(nlogn)$

先对potions排序，然后对spells的每一个元素，拿到排序后的potions中二分搜索小于target的最大下标，计算出满足条件的元素个数。

public int[] successfulPairs(int[] spells, int[] potions, long success) {
    Arrays.sort(potions);
    int[] res = new int[spells.length];
    for (int i = 0; i < spells.length; i++) {
        int index = binarySearch(potions, success, spells[i]);
        res[i] = potions.length - index - 1;
    }
    return res;
}

// 寻找小于target元素的最大坐标
public int binarySearch(int[] potions, long target, int base) {
    int left = 0, right = potions.length - 1;
    while (left <= right) {
        int mid = left + (right - left >> 1);
        long midValue = (long) potions[mid] * base;
        if (midValue < target) {
            left = mid + 1;
        } else if (midValue > target) {
            right = mid - 1;
        } else {
            right = mid - 1;
        }
    }
    return right;
}

准时到达的列车最小时速

给你一个浮点数 hour ，表示你到达办公室可用的总通勤时间。要到达办公室，你必须按给定次序乘坐 n 趟列车。另给你一个长度为 n 的整数数组 dist ，其中 dist[i] 表示第 i 趟列车的行驶距离（单位是千米）。

每趟列车均只能在整点发车，所以你可能需要在两趟列车之间等待一段时间。

• 例如，第 1 趟列车需要 1.5 小时，那你必须再等待 0.5 小时，搭乘在第 2 小时发车的第 2 趟列车。

返回能满足你在时限前到达办公室所要求全部列车的 最小正整数 时速（单位：千米每小时），如果无法准时到达，则返回 -1 。

生成的测试用例保证答案不超过 $10^7$ ，且 hour 的 小数点后最多存在两位数字 。

本题 二分的对象是 列车的最小正整数时速，时速的范围为$[1,10^7]$区间的整数。

• 当时速能够满足条件，压缩右侧空间，更新空间[left,mid-1]

• 当时速不能满足条件，压缩左侧空间，更新空间[mid+1,right]

返回满足条件的最小时速 left。当left超过右侧边界时，说明没有时速能够满足条件。

条件的判断：

• 对于除最后一个车次外，其他车次如果 距离/速度 能够整除就取用该整数，如果无法整除，需要向上取整。

• 对于最后一个车次，需要保留 距离/速度 的小数部分

当所有车次使用的时间总和小于给定的hour,当前速度可以满足，否则不满足。

public int minSpeedOnTime(int[] dist, double hour) {
    int max = 10_000_000;
    int left = 1, right = max;
    while (left <= right) {
        int mid = left + (right - left >> 1);
        if (satisfy(dist, hour, mid)) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    if (left > max) {
        return -1;
    } else {
        return left;
    }
}

public boolean satisfy(int[] dist, double hour, int speed) {
    double ans = 0;
    for (int i = 0; i < dist.length - 1; i++) {
        ans += (dist[i] % speed == 0 ? dist[i] / speed : dist[i] / speed + 1);
    }
    ans += (double) dist[dist.length - 1] / speed;
    return ans > hour ? false : true;
}

两数之和

双指针实现：$O(n)$

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

二分搜索实现：$O(nlog(n))$

public int[] twoSum(int[] numbers, int target) {
    for (int i = 0; i < numbers.length; i++) {
        int val = target - numbers[i];
        int index = binarySearch(numbers, i + 1, numbers.length - 1, val);
        if (index != -1) {
            return new int[] { i + 1, index + 1 };
        }
    }
    return null;
}

public static int binarySearch(int[] arr, int start, int end, int val) {
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (arr[mid] == val) {
            return mid;
        } else if (arr[mid] > val) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    return -1;
}