双指针查找与常用算法框架

双指针技巧详解

主要分为两类：1、快慢指针；2、左右指针；前者主要解决链表中的问题，比如典型的判定链表中是否包含环；后者主要解决数组（或字符串）中的问题，比如：二分查找。

链表、子串、数组的题目，一般都需要用到双指针技巧。

链表指针数组题，用双指针别犹豫。

双指针家三兄弟，各个都是万人迷。

快慢指针最神奇，链表操作无压力。

归并排序找中点，链表成环搞判定。

左右指针最常见，左右两端相向行。

反转数组要靠它，二分搜索是弟弟。

滑动窗口老猛男，子串问题全靠它。

左右指针滑窗口，一前一后齐头进。

快慢指针的用法

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

判定链表中是否有环

单链表的特点是每个节点只知道下⼀个节点，所以⼀个指针的话⽆法判断链 表中是否含有环的。 如果链表中不含环，那么这个指针最终会遇到空指针 null 表⽰链表到头 了，这还好说，可以判断该链表不含环。但是如果链表中含有环，那么这个指针就会陷⼊死循环，因为环形数组中没 有 null 指针作为尾部节点。

经典解法就是⽤两个指针，⼀个跑得快，⼀个跑得慢。如果不含有环，跑得 快的那个指针最终会遇到 null，说明链表不含环；如果含有环，快指针最终 会超慢指针⼀圈，和慢指针相遇，说明链表含有环。

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

已知链表中有环，返回其起始位置

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

第⼀次相遇时，假设慢指针 slow ⾛了 k 步，那么快指针 fast ⼀定⾛了 2k 步，也就是说⽐ slow 多⾛了 k 步（也就是环的⻓度）。设相遇点距环的起点的距离为 m，那么环的起点距头结点 head 的距离为 k - m，也就是说如果从 head 前进 k - m 步就能到达环起点。 巧的是，如果从相遇点继续前进 k - m 步，也恰好到达环起点。 所以，只要我们把快慢指针中的任⼀个重新指向 head，然后两个指针同速 前进，k - m 步后就会相遇，相遇之处就是环的起点了

ListNode detectCycle(ListNode head) { 
    ListNode fast, slow; 
    fast = slow = head; 
    while (fast != null && fast.next != null) { 
        fast = fast.next.next; 
        slow = slow.next; 
        if (fast == slow) 
            break; 
    }// 上⾯的代码类似 hasCycle 函数
        slow = head; 
    while (slow != fast) { 
        fast = fast.next; 
        slow = slow.next; 
    }
    return slow; 
}

寻找链表的中点

类似上⾯的思路，我们还可以让快指针⼀次前进两步，慢指针⼀次前进⼀ 步，当快指针到达链表尽头时，慢指针就处于链表的中间位置。当链表的⻓度是奇数时，slow 恰巧停在中点位置；如果⻓度是偶数，slow 最终的位置是中间偏右。

寻找链表中点的⼀个重要作⽤是对链表进⾏归并排序。 回想数组的归并排序：求中点索引递归地把数组⼆分，最后合并两个有序数 组。对于链表，合并两个有序链表是很简单的，难点就在于⼆分。 但是现在你学会了找到链表的中点，就能实现链表的⼆分了。

while (fast != null && fast.next != null) { 
    fast = fast.next.next;
    slow = slow.next; 
}// slow 就在中间位置 
return slow;

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

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

ListNode slow, fast; 
slow = fast = head; 
while (k-- > 0) 
    fast = fast.next; 
while (fast != null) { 
    slow = slow.next; 
    fast = fast.next; }
return slow;

左右指针的常见用法

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

二分查找

int binarySearch(int[] nums, int target) { 
    int left = 0; 
    int right = nums.length - 1;
    while(left <= right) { 
        int mid = (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; 
}

二数之和

给定一个已经按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回两个下标值index1和index2。

只要数组有序就应该想到双指针用法，解法类似于二分查找，通过调节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) { // 题⽬要求的索引是从 1 开始的
            return new int[]{left + 1, right + 1}; 
        } 
        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) { 
        // swap(nums[left], nums[right]) 
        int temp = nums[left]; 
        nums[left] = nums[right]; 
        nums[right] = temp; 
        left++; 
        right--; 
    } 
}

滑动窗口算法

滑动窗口是双指针技巧的最高境界，可以解决一大类子字符串匹配的问题，比如：最小覆盖子串、字符串的排列、找到字符串中所有字母异位词、无重复字符的最长子串。其实算法的技巧思路特别简单，即维护一个窗口，不断滑动并更新答案。

int left = 0, right = 0;
while (right < s.size()) {
    // 增⼤窗⼝ 
    window.add(s[right]); 
    right++; 
    
    while (window needs shrink) { 
        // 缩⼩窗⼝ 
        window.remove(s[left]); 
        left++; 
    } 
}

这个算法技巧的时间复杂度是 O(N)，⽐字符串暴⼒算法要⾼效得多。 其实困扰⼤家的，不是算法的思路，⽽是各种细节问题。⽐如说如何向窗⼝ 中添加新元素，如何缩⼩窗⼝，在窗⼝滑动的哪个阶段更新结果。即便你明 ⽩了这些细节，也容易出 bug，找 bug 还不知道怎么找，真的挺让⼈⼼烦 的。

所以今天我就写⼀套滑动窗⼝算法的代码框架，我连再哪⾥做输出 debug 都给你写好了，以后遇到相关的问题，你就默写出来如下框架然后改三个地 ⽅就⾏，还不会出 bug：

/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0; 
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        printf("window: [%d, %d)\n", left, right);
        /********************/

        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

而且，这两个...处的操作分别是右移和左移窗口更新操作，等会你会发现它们操作是完全对称的。本文代码为 C++ 实现，不会用到什么编程方面的奇技淫巧，但是还是简单介绍一下一些用到的数据结构，以免有的读者因为语言的细节问题阻碍对算法思想的理解：

unordered_map就是哈希表（字典），它的一个方法count(key)相当于 Java 的containsKey(key)可以判断键 key 是否存在。可以使用方括号访问键对应的值map[key]。需要注意的是，如果该key不存在，C++ 会自动创建这个 key，并把map[key]赋值为 0。所以代码中多次出现的map[key]++相当于 Java 的map.put(key, map.getOrDefault(key, 0) + 1)。

最小覆盖子串

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

就是说要在S(source) 中找到包含T(target) 中全部字母的一个子串，且这个子串一定是所有可能子串中最短的。

如果我们使用暴力解法，代码大概是这样的：

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

而滑动窗口的思路是这样的：

1、我们在字符串S中使用双指针中的左右指针技巧，初始化left = right = 0，把索引左闭右开区间[left, right)称为一个「窗口」。

2、我们先不断地增加right指针扩大窗口[left, right)，直到窗口中的字符串符合要求（包含了T中的所有字符）。

3、此时，我们停止增加right，转而不断增加left指针缩小窗口[left, right)，直到窗口中的字符串不再符合要求（不包含T中的所有字符了）。同时，每次增加left，我们都要更新一轮结果。

4、重复第 2 和第 3 步，直到right到达字符串S的尽头

这个思路其实也不难，第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解，也就是最短的覆盖子串。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动，这就是「滑动窗口」这个名字的来历。下面画图理解一下，needs和window相当于计数器，分别记录T中字符出现次数和「窗口」中的相应字符的出现次数。

//首先，初始化window和need两个哈希表，记录窗口中的字符和需要凑齐的字符：
unordered_map<char, int> need, window;
for (char c : t) need[c]++;//为每个键值赋值

//然后，使用left和right变量初始化窗口的两端，不要忘了，区间[left, right)是左闭右开的，所以初始情况下窗口没有包含任何元素：
int left = 0, right = 0;
int valid = 0; 
while (right < s.size()) {
    // 开始滑动
}
//其中valid变量表示窗口中满足need条件的字符个数，如果valid和need.size的大小相同，则说明窗口已满足条件，已经完全覆盖了串T。
//现在开始套模板，只需要思考以下四个问题：
//1、当移动right扩大窗口，即加入字符时，应该更新哪些数据？
//2、什么条件下，窗口应该暂停扩大，开始移动left缩小窗口？
//3、当移动left缩小窗口，即移出字符时，应该更新哪些数据？
//4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？

//如果一个字符进入窗口，应该增加window计数器；如果一个字符将移出窗口的时候，应该减少window计数器；当valid满足need时应该收缩窗口；应该在收缩窗口的时候更新最终结果。

string minWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0;
    // 记录最小覆盖子串的起始索引及长度
    int start = 0, len = INT_MAX;
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c])
                valid++;
        }

        // 判断左侧窗口是否要收缩
        while (valid == need.size()) {
            // 在这里更新最小覆盖子串
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            // d 是将移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            if (need.count(d)) {
                if (window[d] == need[d])
                    valid--;
                window[d]--;
            }                    
        }
    }
    // 返回最小覆盖子串
    return len == INT_MAX ?
        "" : s.substr(start, len);
}

需要注意的是，当我们发现某个字符在window的数量满足了need的需要，就要更新valid，表示有一个字符已经满足要求。而且，你能发现，两次对窗口内数据的更新操作是完全对称的。

当valid == need.size()时，说明T中所有字符已经被覆盖，已经得到一个可行的覆盖子串，现在应该开始收缩窗口了，以便得到「最小覆盖子串」。移动left收缩窗口时，窗口内的字符都是可行解，所以应该在收缩窗口的阶段进行最小覆盖子串的更新，以便从可行解中找到长度最短的最终结果。

至此，应该可以完全理解这套框架了，滑动窗口算法又不难，就是细节问题让人烦得很。以后遇到滑动窗口算法，你就按照这框架写代码，保准没有 bug，还省事儿。

字符串排列

题目：给定两个字符串S1、S2，写一个函数来判断S2是否包含S1的序列；即第一个字符串的排列之一是第二个字符串的子串

这种题目，是明显的滑动窗口算法，相当给你一个S和一个T，请问你S中是否存在一个子串，包含T中所有字符且不包含其他字符？首先，先复制粘贴之前的算法框架代码，然后明确刚才提出的 4 个问题，即可写出这道题的答案：

// 判断 s 中是否存在 t 的排列
bool checkInclusion(string t, string s) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0;
    while (right < s.size()) {
        char c = s[right];
        right++;
        // 进行窗口内数据的一系列更新
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c])
                valid++;
        }

        // 判断左侧窗口是否要收缩
        while (right - left >= t.size()) {
            // 在这里判断是否找到了合法的子串
            if (valid == need.size())
                return true;
            char d = s[left];
            left++;
            // 进行窗口内数据的一系列更新
            if (need.count(d)) {
                if (window[d] == need[d])
                    valid--;
                window[d]--;
            }
        }
    }
    // 未找到符合条件的子串
    return false;
}

对于这道题的解法代码，基本上和最小覆盖子串一模一样，只需要改变两个地方：

1、本题移动left缩小窗口的时机是窗口大小大于t.size()时，因为排列嘛，显然长度应该是一样的。

2、当发现valid == need.size()时，就说明窗口中就是一个合法的排列，所以立即返回true。

至于如何处理窗口的扩大和缩小，和最小覆盖子串完全相同。

找所有字母异位词

给定一个字符串s和非空字符串p，找到s中所有是p的字母异位词的子串，返回这些子串的起始索引。（字母异位词指字母相同，但排列不同的字符串；不考虑答案输出的顺序）

呵呵，这个所谓的字母异位词，不就是排列吗，搞个高端的说法就能糊弄人了吗？相当于，输入一个串S，一个串T，找到S中所有T的排列，返回它们的起始索引。直接默写一下框架，明确刚才讲的 4 个问题，即可秒杀这道题：

vector<int> findAnagrams(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0;
    vector<int> res; // 记录结果
    while (right < s.size()) {
        char c = s[right];
        right++;
        // 进行窗口内数据的一系列更新
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c]) 
                valid++;
        }
        // 判断左侧窗口是否要收缩
        while (right - left >= t.size()) {
            // 当窗口符合条件时，把起始索引加入 res
            if (valid == need.size())
                res.push_back(left);
            char d = s[left];
            left++;
            // 进行窗口内数据的一系列更新
            if (need.count(d)) {
                if (window[d] == need[d])
                    valid--;
                window[d]--;
            }
        }
    }
    return res;
}

跟寻找字符串的排列一样，只是找到一个合法异位词（排列）之后将起始索引加入res即可

最长无重复子串

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

这个题终于有了点新意，不是一套框架就出答案，不过反而更简单了，稍微改一改框架就行了：

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> window;

    int left = 0, right = 0;
    int res = 0; // 记录结果
    while (right < s.size()) {
        char c = s[right];
        right++;
        // 进行窗口内数据的一系列更新
        window[c]++;
        // 判断左侧窗口是否要收缩
        while (window[c] > 1) {
            char d = s[left];
            left++;
            // 进行窗口内数据的一系列更新
            window[d]--;
        }
        // 在这里更新答案
        res = max(res, right - left);
    }
    return res;
}

这就是变简单了，连need和valid都不需要，而且更新窗口内数据也只需要简单的更新计数器window即可。

当window[c]值大于 1 时，说明窗口中存在重复字符，不符合条件，就该移动left缩小窗口了嘛。唯一需要注意的是，在哪里更新结果res呢？我们要的是最长无重复子串，哪一个阶段可以保证窗口中的字符串是没有重复的呢？

这里和之前不一样，**要在收缩窗口完成后更新res**，因为窗口收缩的 while 条件是存在重复元素，换句话说收缩完成后一定保证窗口中没有重复嘛。

twoSum问题的核心思想

第一题

这个问题的最基本形式是这样：给你⼀个数组和⼀个整数 target ，可以保 证数组中存在两个数的和为 target ，请你返回这两个数的索引。这个问题如何解决呢？⾸先最简单粗暴的办法当然是穷举了：

int[] twoSum(int[] nums, int target) { 
    for (int i = 0; i < nums.length; i++) 
        for (int j = i + 1; j < nums.length; j++) 
            if (nums[j] == target - nums[i]) 
                return new int[] { i, j }; 
    // 不存在这么两个数 
    return new int[] {-1, -1}; 
}

这个解法⾮常直接，时间复杂度 O(N^2)，空间复杂度 O(1)。 可以通过⼀个哈希表减少时间复杂度：

int[] twoSum(int[] nums, int target) { 
    int n = nums.length; 
    index<Integer, Integer> 
        index = new HashMap<>();
    // 构造⼀个哈希表：元素映射到相应的索引 
    for (int i = 0; i < n; i++) 
        index.put(nums[i], i); 
    for (int i = 0; i < n; i++) { 
        int other = target - nums[i]; 
        // 如果 other 存在且不是 nums[i] 本⾝ 
        if (index.containsKey(other) && index.get(other) != i) 
            return new int[] {i, index.get(other)}; 
    }
    return new int[] {-1, -1};
}

这样，由于哈希表的查询时间为 O(1)，算法的时间复杂度降低到 O(N)，但 是需要 O(N) 的空间复杂度来存储哈希表。不过综合来看，是要⽐暴⼒解法 ⾼效的。

我觉得 Two Sum 系列问题就是想教我们如何使⽤哈希表处理问题。我们接 着往后看。

第二题

这⾥我们稍微修改⼀下上⾯的问题。我们设计⼀个类，拥有两个 API：

class TwoSum { 
    // 向数据结构中添加⼀个数 number 
    public void add(int number); 
    // 寻找当前数据结构中是否存在两个数的和为 value 
    public boolean find(int value); 
}

如何实现这两个 API 呢，我们可以仿照上⼀道题⽬，使⽤⼀个哈希表辅助 find ⽅法：

class TwoSum { 
    Map<Integer, Integer> freq = new HashMap<>();
    public void add(int number) { 
        // 记录 number 出现的次数 
        freq.put(number, freq.getOrDefault(number, 0) + 1); 
    }
    
    public boolean find(int value) { 
        for (Integer key : freq.keySet()) { 
            int other = value - key; 
            // 情况⼀ 
            if (other == key && freq.get(key) > 1) 
                return true;
            // 情况⼆ 
            if (other != key && freq.containsKey(other)) 
                return true; 
        }
        return false; 
    } 
}

进⾏ find 的时候有两种情况，举个例⼦：

情况⼀： add 了 [3,3,2,5] 之后，执⾏ find(6) ，由于 3 出现了两次，3 + 3 = 6，所以返回 true。

情况⼆： add 了 [3,3,2,5] 之后，执⾏ find(7) ，那么 key 为 2， other 为 5 时算法可以返回 true。

除了上述两种情况外， find 只能返回 false 了。

对于这个解法的时间复杂度呢， add ⽅法是 O(1)， find ⽅法是 O(N)，空 间复杂度为 O(N)，和上⼀道题⽬⽐较类似。但是对于 API 的设计，是需要考虑现实情况的。⽐如说，我们设计的这个 类，使⽤ find ⽅法⾮常频繁，那么每次都要 O(N) 的时间，岂不是很浪费 费时间吗？对于这种情况，我们是否可以做些优化呢？

是的，对于频繁使⽤ find ⽅法的场景，我们可以进⾏优化。我们可以参 考上⼀道题⽬的暴⼒解法，借助哈希集合来针对性优化 find ⽅法：

class TwoSum {
    Set<Integer> sum = new HashSet<>(); 
    List<Integer> nums = new ArrayList<>(); 
    
    public void add(int number) { 
        // 记录所有可能组成的和 
        for (int n : nums) 
            sum.add(n + number); 
        nums.add(number); 
    }
    public boolean find(int value) { 
        return sum.contains(value); 
    } 
}

这样 sum 中就储存了所有加⼊数字可能组成的和，每次 find 只要花费 O(1) 的时间在集合中判断⼀下是否存在就⾏了，显然⾮常适合频繁使⽤ find 的场景。

对于 TwoSum 问题，⼀个难点就是给的数组⽆序。对于⼀个⽆序的数组， 我们似乎什么技巧也没有，只能暴⼒穷举所有可能。

⼀般情况下，我们会⾸先把数组排序再考虑双指针技巧。TwoSum 启发我 们，HashMap 或者 HashSet 也可以帮助我们处理⽆序数组相关的简单问题。 另外，设计的核⼼在于权衡，利⽤不同的数据结构，可以得到⼀些针对性的 加强。

最后，如果 TwoSum I 中给的数组是有序的，应该如何编写算法呢？答案很 简单，前⽂「双指针技巧汇总」写过：

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}; 
}

二分查找详解

⼆分查找并不简单，Knuth ⼤佬（发明 KMP 算法的那位）都说⼆分查找：

思路很简单，细节是魔⿁。很多⼈喜欢拿整型溢出的 bug 说事⼉，但是⼆分 查找真正的坑根本就不是那个细节问题，⽽是在于到底要给 mid 加⼀还是 减⼀，while ⾥到底⽤ <= 还是 < 。

二分搜索诗

管他左侧还右侧，搜索区间定乾坤。

搜索一个元素时，搜索区间两端闭。

while条件带等号，否则需要打补丁。

if相等就返回，其他的事甭操心。

mid必须加减一，因为区间两端闭。

while结束就凉凉，凄凄惨惨返-1。

搜索左右边界时，搜索区间要阐明。

左闭右开最常见，其余逻辑便自明。

while要用小于号，这样才能不漏掉。

if相等别返回，利用mid锁边界。

mid加一或减一？要看区间区间开或闭。

while结束不算完，因为你还没返回。

索引可能出边界，if检查保平安。

二分查找框架

int binarySearch(int[] nums, int target) { 
    int left = 0, right = ...; 
    while(...) { 
        int mid = left + (right - left) / 2; 
        if (nums[mid] == target) { 
            ... 
        } else if (nums[mid] < target) { 
            left = ... 
        } else if (nums[mid] > target) { 
            right = ... 
        } 
    }
    return ...; 
}

分析⼆分查找的⼀个技巧是：不要出现 else**，⽽是把所有情况⽤** else if 写清 楚，这样可以清楚地展现所有细节。本⽂都会使⽤ else if，旨在讲清楚。

其中 … 标记的部分，就是可能出现细节问题的地⽅，当你⻅到⼀个⼆分 查找的代码时，⾸先注意这⼏个地⽅。后⽂⽤实例分析这些地⽅能有什么样 的变化。

另外声明⼀下，计算 mid 时需要防⽌溢出，代码中 left + (right - left) / 2 就和 (left + right) / 2 的结果相同，但是有效防⽌了 left 和right 太⼤直接相加导致溢出

寻找一个数：基本二分查找

这个场景是最简单的，肯能也是⼤家最熟悉的，即搜索⼀个数，如果存在， 返回其索引，否则返回 -1。

int binarySearch(int[] nums, int target) { 
    int left = 0;
    int right = 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; 
}

1**、为什么** while 循环的条件中是 <=**，⽽不是** **<**？

答：因为初始化 right 的赋值是 nums.length - 1 ，即最后⼀个元素的索 引，⽽不是 nums.length 。

这⼆者可能出现在不同功能的⼆分查找中，区别是：前者相当于两端都闭区 间 [left, right] ，后者相当于左闭右开区间 [left, right) ，因为索引⼤⼩为 nums.length 是越界的。

我们这个算法中使⽤的是前者 [left, right] 两端都闭的区间。这个区间

其实就是每次进⾏搜索的区间。

2、什么时候应该停⽌搜索呢？

当然，找到了⽬标值的时候可以终⽌：

if(nums[mid] == target) return mid;

但如果没找到，就需要 while 循环终⽌，然后返回 -1。那 while 循环什么时 候应该终⽌？搜索区间为空的时候应该终⽌，意味着你没得找了，就等于没 找到嘛。

while(left <= right) 的终⽌条件是 left == right + 1 ，写成区间的形式 就是 [right + 1, right] ，或者带个具体的数字进去 [3, 2] ，可⻅这时候 区间为空，

while(left < right) 的终⽌条件是 left == right ，写成区间的形式就是 [left, right] ，或者带个具体的数字进去 [2, 2] ，这时候区间⾮空，还 有⼀个数 2，但此时 while 循环终⽌了。也就是说这区间 [2, 2] 被漏掉 了，索引 2 没有被搜索，如果这时候直接返回 -1 就是错误的。

3**、为什么** left = mid + 1 ， right = mid - 1 ？我看有的代码是 right = mid 或者 left = mid ，没有这些加加减减，到底怎么回事，怎么判断？

答：这也是⼆分查找的⼀个难点，不过只要你能理解前⾯的内容，就能够很 容易判断。

刚才明确了「搜索区间」这个概念，⽽且本算法的搜索区间是两端都闭的， 即 [left, right] 。那么当我们发现索引 mid 不是要找的 target 时，下 ⼀步应该去搜索哪⾥呢？ 当然是去搜索 [left, mid-1] 或者 [mid+1, right] 对不对？因为 mid 已 经搜索过，应该从搜索区间中去除。

4**、此算法有什么缺陷**？

答：⾄此，你应该已经掌握了该算法的所有细节，以及这样处理的原因。但 是，这个算法存在局限性。

⽐如说给你有序数组 nums = [1,2,2,2,3] ， target 为 2，此算法返回的索 引是 2，没错。但是如果我想得到 target 的左侧边界，即索引 1，或者我 想得到 target 的右侧边界，即索引 3，这样的话此算法是⽆法处理的。

寻找左侧边界的⼆分搜索

int left_bound(int[] nums, int target) { 
    if (nums.length == 0) return -1; 
    int left = 0; 
    int right = nums.length; // 注意 
    while (left < right) { // 注意 
        int mid = (left + right) / 2; 
        if (nums[mid] == target) { 
            right = mid; 
        } else if (nums[mid] < target) { 
            left = mid + 1; 
        } else if (nums[mid] > target) { 
            right = mid; // 注意 
        } 
    }
    return left; 
}

1**、为什么** while 中是 < ⽽不是 <= ?

答：⽤相同的⽅法分析，因为 right = nums.length ⽽不是 nums.length - 1 。因此每次循环的「搜索区间」是 [left, right) 左闭右开。 while(left < right) 终⽌的条件是 left == right ，此时搜索区间 [left, left) 为空，所以可以正确终⽌。

寻找右侧边界的⼆分查找

int right_bound(int[] nums, int target) { 
    if (nums.length == 0) return -1; 
    int left = 0, right = nums.length; 
    
    while (left < right) { 
        int mid = (left + right) / 2; 
        if (nums[mid] == target) { 
            left = mid + 1; // 注意 
        } else if (nums[mid] < target) {
            left = mid + 1; 
        } else if (nums[mid] > target) { 
            right = mid; 
        } 
    }return left - 1; // 注意 
}

字符串乘法

对于⽐较⼩的数字，做运算可以直接使⽤编程语⾔提供的运算符，但是如果 相乘的两个因数⾮常⼤，语⾔提供的数据类型可能就会溢出。⼀种替代⽅案 就是，运算数以字符串的形式输⼊，然后模仿我们⼩学学习的乘法算术过程 计算出结果，并且也⽤字符串表⽰。

题目

给定两个以字符串形式表示的非负整数num1、num2，返回num1和num2的乘积，它们的乘积也表示为字符串的形式。

需要注意的是， num1 和 num2 可以⾮常⻓，所以不可以把他们直接转成 整型然后运算，唯⼀的思路就是模仿我们⼿算乘法。

思路

计算 123 × 5 ，再计算 123 × 4 ，最后错⼀位相加。这个流程恐怕⼩学⽣ 都可以熟练完成，但是你是否能把这个运算过程进⼀步机械化，写成⼀套算 法指令让没有任何智商的计算机来执⾏呢？

你看这个简单过程，其中涉及乘法进位，涉及错位相加，还涉及加法进位； ⽽且还有⼀些不易察觉的问题，⽐如说两位数乘以两位数，结果可能是四位 数，也可能是三位数，你怎么想出⼀个标准化的处理⽅式？这就是算法的魅 ⼒，如果没有计算机思维，简单的问题可能都没办法⾃动化处理。

⾸先，我们这种⼿算⽅式还是太「⾼级」了，我们要再「低级」⼀点， 123 × 5 和 123 × 4 的过程还可以进⼀步分解，最后再相加：

现在 123 并不⼤，如果是个很⼤的数字的话，是⽆法直接计算乘积的。我 们可以⽤⼀个数组在底下接收相加结果：

整个计算过程⼤概是这样，有两个指针 *i**，j 在 num1 和 num2 上游⾛，

计算乘积，同时将乘积叠加到 res 的正确位置： 现在还有⼀个关键问题，如何将乘积叠加到 res 的正确位置，或者说，如 何通过 i，j 计算 res 的对应索引呢？ 其实，细⼼观察之后就发现， num1[i] 和 num2[j] 的乘积对应的就是 res[i+j] 和 res[i+j+1] 这两个位置。

明⽩了这⼀点，就可以⽤代码模仿出这个计算过程了：

string multiply(string num1, string num2) { 
    int m = num1.size(), n = num2.size(); 
    // 结果最多为 m + n 位数 
    vector<int> res(m + n, 0); 
    // 从个位数开始逐位相乘 
    for (int i = m - 1; i >= 0; i--) 
        for (int j = n - 1; j >= 0; j--) { 
            int mul = (num1[i]-'0') * (num2[j]-'0'); 
            // 乘积在 res 对应的索引位置 
            int p1 = i + j, p2 = i + j + 1; 
            // 叠加到 res 上 
            int sum = mul + res[p2]; 
            res[p2] = sum % 10; 
            res[p1] += sum / 10; 
        } 
    // 结果前缀可能存的 0（未使⽤的位） 
    int i = 0; 
    while (i < res.size() && res[i] == 0) 
        i++; 
    // 将计算结果转化成字符串 
    string str; 
    for (; i < res.size(); i++) 
        str.push_back('0' + res[i]); 
    return str.size() == 0 ? "0" : str; 
}

总结⼀下，我们习以为常的⼀些思维⽅式，在计算机看来是⾮常难以做到 的。⽐如说我们习惯的算术流程并不复杂，但是如果让你再进⼀步，翻译成 代码逻辑，并不简单。算法需要将计算流程再简化，通过边算边叠加的⽅式 来得到结果。

俗话教育我们，不要陷⼊思维定式，不要程序化，要发散思维，要创新。但 我觉得程序化并不是坏事，可以⼤幅提⾼效率，减⼩失误率。算法不就是⼀ 套程序化的思维吗，只有程序化才能让计算机帮助我们解决复杂问题呀！

前缀和技巧

题目：

算出⼀共有⼏个和为 k 的⼦数组。给定一个整数数组和一个整数k，你需要找到该数组中和为k的连续的子数组的个数。

输入：nums = [1,1,1], k = 2；输出：2，[1,1]与[1,1]为两种不同的情况。

解法思路：

那我把所有⼦数组都穷举出来，算它们的和，看看谁的和等于 k 不就⾏了。 关键是，如何快速得到某个⼦数组的和呢，⽐如说给你⼀个数组 nums ，让 你实现⼀个接⼝ sum(i, j) ，这个接⼝要返回 nums[i..j] 的和，⽽且会被 多次调⽤，你怎么实现这个接⼝呢？

因为接⼝要被多次调⽤，显然不能每次都去遍历 nums[i..j] ，有没有⼀种 快速的⽅法在 O(1) 时间内算出 nums[i..j] 呢？这就需要前缀和技巧了。

什么是前缀和

前缀和的思路是这样的，对于⼀个给定的数组 nums ，我们额外开辟⼀个前 缀和数组进⾏预处理：

int n = nums.length; // 前缀和数组
int[] preSum = new int[n + 1]; 
preSum[0] = 0; 
for (int i = 0; i < n; i++) 
    preSum[i + 1] = preSum[i] + nums[i];

这个前缀和数组 preSum 的含义也很好理解， preSum[i] 就是 nums[0..i- 1] 的和。那么如果我们想求 nums[i..j] 的和，只需要⼀步操作

preSum[j+1]-preSum[i] 即可，⽽不需要重新去遍历数组了。

回到这个⼦数组问题，我们想求有多少个⼦数组的和为 k，借助前缀和技巧

很容易写出⼀个解法：

int subarraySum(int[] nums, int k) { 
    int n = nums.length; 
    // 构造前缀和 
    int[] sum = new int[n + 1]; 
    sum[0] = 0; 
    for (int i = 0; i < n; i++) 
        sum[i + 1] = sum[i] + nums[i]; 
    int ans = 0; // 穷举所有⼦数组 
    for (int i = 1; i <= n; i++) 
        for (int j = 0; j < i; j++)
            // sum of nums[j..i-1] 
            if (sum[i] - sum[j] == k) 
                ans++; 
    return ans; 
}

这个解法的时间复杂度 O(N^2) 空间复杂度 O(N) ，并不是最优的解法。不 过通过这个解法理解了前缀和数组的⼯作原理之后，可以使⽤⼀些巧妙的办 法把时间复杂度进⼀步降低

优化解法

//前⾯的解法有嵌套的 for 循环：
for (int i = 1; i <= n; i++) 
    for (int j = 0; j < i; j++) 
        if (sum[i] - sum[j] == k) 
            ans++;
//第⼆层 for 循环在⼲嘛呢？翻译⼀下就是，在计算，有⼏个 j 能够使得 sum[i] 和 sum[j] 的差为 k。毎找到⼀个这样的 j ，就把结果加⼀。 我们可以把 if 语句⾥的条件判断移项，这样写：
if (sum[j] == sum[i] - k) 
    ans++;
//优化的思路是：我直接记录下有⼏个 sum[j] 和 sum[i] - k 相等，直接更 新结果，就避免了内层的 for 循环。
//我们可以⽤哈希表，在记录前缀和的同 时记录该前缀和出现的次数。
int subarraySum(int[] nums, int k) { 
    int n = nums.length; // map：前缀和 -> 该前缀和出现的次数 
    HashMap<Integer, Integer>;
    preSum = new HashMap<>(); 
    // base case 
    preSum.put(0, 1); 
    
    int ans = 0, sum0_i = 0; 
    for (int i = 0; i < n; i++) { 
        sum0_i += nums[i]; 
        // 这是我们想找的前缀和 nums[0..j] 
        int sum0_j = sum0_i - k; 
        // 如果前⾯有这个前缀和，则直接更新答案 
        if (preSum.containsKey(sum0_j)) 
            ans += preSum.get(sum0_j); 
        // 把前缀和 nums[0..i] 加⼊并记录出现次数 
        preSum.put(sum0_i, preSum.getOrDefault(sum0_i, 0) + 1); 
    }
    return ans; 
}

这样，就把时间复杂度降到了 O(N) ，是最优解法了。

总结

前缀和不难，却很有⽤，主要⽤于处理数组区间的问题。 ⽐如说，让你统计班上同学考试成绩在不同分数段的百分⽐，也可以利⽤前 缀和技巧

int[] scores; // 存储着所有同学的分数 
// 试卷满分 150 分 
int[] count = new int[150 + 1] // 记录每个分数有⼏个同学 
    for (int score : scores)
        count[score]++;
// 构造前缀和 
for (int i = 1; i < count.length; i++) 
    count[i] = count[i] + count[i-1];

这样，给你任何⼀个分数段，你都能通过前缀和相减快速计算出这个分数段 \的⼈数，百分⽐也就很容易计算了。

但是，稍微复杂⼀些的算法问题，不⽌考察简单的前缀和技巧。⽐如本⽂探 讨的这道题⽬，就需要借助前缀和的思路做进⼀步的优化，借助哈希表去除 不必要的嵌套循环。可⻅对题⽬的理解和细节的分析能⼒对于算法的优化是 ⾄关重要的。