双指针

Posted May 3, 2026

37 min read

双指针

双指针顾名思义是有两个变量，分别指向不同的位置。
双指针可以分为：
同向指针（快慢指针，滑动窗口）
反向指针（二分搜索）

同向指针

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

快慢指针

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

判断链表中是否有环

如果链表中没有环，一个指针从头遍历，最终一定会走到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)$级别内解决。

解法：

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

首先移动right向前移动s1的长度，将字符放入到滑动窗口
对满足s1长度滑动窗口的子串进行判断，是否是s2字符串的排列
然后同步移动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。

步骤：

左指针指向数组开始，右指针指向数组结尾
计算数组的中间位置mid
若目标值target大于中间值num[mid]，则说明目标值在右侧区间，让left=mid+1；若目标值target小于中间值num[mid]，则说明目标值在左侧区间，让right=mid-1;若目标值target等于中间值num[mid]，则找到目标值，直接返回。
更新数组区间[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;
}

两数之和

双指针实现：$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;
}

leetcode

leetcode two pointer

This post is licensed under CC BY 4.0 by the author.