Optimal Algorithms：滑动窗口+二分查找

一、字符串中所有字母异位词（medium）

1.1 题目链接：

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

1.2 题目描述：

给定两个字符串 s 和 p，找到 s 中所有 p 的
异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

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

示例 2:

输入: s = “abab”, p = “ab”
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。

提示:

• 1 <= s.length, p.length <= 3 * 104
• s 和 p 仅包含小写字母

1.3 题目解析：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FindAllAnagrams {
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s.length() < p.length()) {
            return result;
        }

        // 用于统计字符串p中各字符出现的频次
        Map<Character, Integer> targetMap = new HashMap<>();
        for (char c : p.toCharArray()) {
            targetMap.put(c, targetMap.getOrDefault(c, 0) + 1);
        }

        // 用于统计滑动窗口内各字符出现的频次
        Map<Character, Integer> windowMap = new HashMap<>();
        int left = 0;
        int right = 0;
        int matchCount = 0;
        while (right < s.length()) {
            char rightChar = s.charAt(right);
            windowMap.put(rightChar, windowMap.getOrDefault(rightChar, 0) + 1);
            if (windowMap.get(rightChar).equals(targetMap.get(rightChar))) {
                matchCount++;
            }

            // 当窗口大小等于p的长度时，进行判断
            if (right - left + 1 == p.length()) {
                if (matchCount == targetMap.size()) {
                    result.add(left);
                }
                char leftChar = s.charAt(left);
                if (windowMap.get(leftChar).equals(targetMap.get(leftChar))) {
                    matchCount--;
                }
                windowMap.put(leftChar, windowMap.get(leftChar) - 1);
                if (windowMap.get(leftChar) == 0) {
                    windowMap.remove(leftChar);
                }
                left++;
            }
            right++;
        }
        return result;
    }

    public static void main(String[] args) {
        String s1 = "cbaebabacd";
        String p1 = "abc";
        System.out.println(findAnagrams(s1, p1));

        String s2 = "abab";
        String p2 = "ab";
        System.out.println(findAnagrams(s2, p2));
    }
}

代码具体解释如下：

1.3.1 整体思路

通过一个滑动窗口在字符串 s 上滑动，窗口大小固定为字符串 p 的长度。利用两个哈希表分别统计字符串 p 中字符出现的频次以及滑动窗口内字符出现的频次，通过对比频次来判断窗口内的子串是否是 p 的异位词。

1.3.2 具体步骤

1. 初始化及边界判断：
   • 创建一个列表 result 用于存储符合要求的子串起始索引。首先判断如果 s 的长度小于 p 的长度，直接返回空列表，因为这种情况下不可能存在 p 的异位词子串。
   • 创建 targetMap 哈希表，遍历字符串 p，统计 p 中每个字符出现的频次，使用 getOrDefault 方法来处理字符第一次出现的情况，将其频次初始化为1或者在已有频次基础上加1。
   • 同时创建 windowMap 哈希表，用于后续统计滑动窗口内字符的频次。初始化滑动窗口的左右边界 left 和 right 都为0，以及用于记录匹配字符个数的 matchCount 为0。
2. 滑动窗口移动及判断：
   • 随着 right 指针不断右移扩大窗口，将新进入窗口的字符加入 windowMap 并更新其频次。如果该字符在 windowMap 中的频次与在 targetMap 中的频次相等，说明该字符的匹配个数增加了，将 matchCount 加1。
   • 当窗口大小（right - left + 1）等于 p 的长度时，进行关键判断：
     • 如果 matchCount 等于 targetMap 的大小（意味着窗口内各字符出现的频次与 p 中各字符出现的频次完全一致），则说明当前窗口内的子串是 p 的异位词，将 left（即子串起始索引）加入 result 列表。
     • 接着要准备收缩窗口，将左边界 left 对应的字符从窗口移除，先获取该字符，若该字符在 windowMap 中的频次与在 targetMap 中的频次相等，说明移除这个字符后匹配个数会减少，将 matchCount 减1。然后更新该字符在 windowMap 中的频次，将其减1，如果减到0了，直接从 windowMap 中移除该字符，最后将 left 指针右移一位，实现窗口收缩。
3. 主函数测试：
   在 main 方法中分别给出了题目示例中的两组测试数据，调用 findAnagrams 方法并输出结果，可以验证代码对于不同输入字符串的正确性。

1.4 代码优化

public static List<Integer> findAnagrams(String ss, String pp) {
    List<Integer> ret = new ArrayList<Integer>();
    char[] s = ss.toCharArray();
    char[] p = pp.toCharArray();
    // 统计字符串 p 中每⼀个字符出现的个数
    int[] hash1 = new int[26]; 
    for (char ch : p) {
        hash1[ch - 'a']++;
    }
    // 统计窗⼝中每⼀个字符出现的个数
    int[] hash2 = new int[26]; 
    int m = p.length;
    for (int left = 0, right = 0, count = 0; right < s.length; right++) {
        char in = s[right];
        // 进窗⼝ + 维护 count
        if (++hash2[in - 'a'] <= hash1[in - 'a']) {
            count++;
        }
        // 判断
        if (right - left + 1 > m) {
            char out = s[left++];
            // 出窗⼝ + 维护 count
            if (hash2[out - 'a']-- <= hash1[out - 'a']) {
                count--;
            }
        }
        // 更新结果
        if (count == m) {
            ret.add(left);
        }
    }
    return ret;
}

1.4.1 整体功能概述

这段Java代码的功能是在给定的字符串 ss 中找出所有是字符串 pp 的异位词的子串起始索引，并将这些索引存放在一个 List<Integer> 类型的列表中返回。它通过滑动窗口的思想，结合使用两个长度为26的整数数组来统计字符出现的频次，以此判断子串是否为异位词。

1.4.2 代码详细解析

1. 初始化部分：

List<Integer> ret = new ArrayList<Integer>();
char[] s = ss.toCharArray();
char[] p = pp.toCharArray();
// 统计字符串 p 中每⼀个字符出现的个数
int[] hash1 = new int[26]; 
for (char ch : p) {
    hash1[ch - 'a']++;
}
// 统计窗⼝中每⼀个字符出现的个数
int[] hash2 = new int[26]; 
int m = p.length;

首先创建了一个 ArrayList 类型的列表 ret，用于存储最终找到的符合要求的子串起始索引。

• 将输入的字符串 ss 和 pp 分别转换为字符数组 s 和 p，方便后续按字符进行操作。
• 创建了两个长度为26的整数数组 hash1 和 hash2，这里利用了英文字母总共26个的特性（小写字母 a - z），hash1 数组用于统计字符串 p 中每个字符出现的次数，通过遍历 p 字符数组，将对应字符（以 ch - 'a' 作为数组下标，ch - 'a' 的值范围是0 - 25，对应 a - z 这26个字母）在 hash1 数组中的计数加1。hash2 数组则用于统计滑动窗口内字符出现的个数，初始化为全0。
• 记录字符串 p 的长度 m，用于后续判断滑动窗口的大小是否达到要求等操作。

2. 滑动窗口循环部分（核心逻辑）：

for (int left = 0, right = 0, count = 0; right < s.length; right++) {

• 这里使用了一个 for 循环来模拟滑动窗口在字符串 s 上的移动，同时初始化了三个变量：
  • left 表示滑动窗口的左边界，初始化为0。
  • right 表示滑动窗口的右边界，也初始化为0，并且随着循环每次向右移动一位（通过 right++，循环条件控制其不会越界）。
  • count 用于统计当前滑动窗口内与字符串 p 中字符匹配的个数，初始化为0。

3. 窗口内字符进入处理及匹配计数维护：

char in = s[right];
// 进窗⼝ + 维护 count
if (++hash2[in - 'a'] <= hash1[in - 'a']) {
    count++;
}

• 当窗口右移（即每次循环）时，获取新进入窗口（通过 right 指针指向的位置）的字符 in。
• 然后将该字符在 hash2 数组中对应的计数加1（++hash2[in - 'a']），表示这个字符在窗口内出现的次数增加了一次。接着判断增加后的计数是否小于等于该字符在 hash1 数组（也就是字符串 p 中该字符出现的次数）中的计数，如果是，则说明这个字符的匹配数量增加了，将 count 加1，表示当前窗口内与字符串 p 匹配的字符个数又多了一个。

4. 窗口大小判断及窗口内字符移出处理和匹配计数维护：

if (right - left + 1 > m) {
    char out = s[left++];
    // 出窗⼝ + 维护 count
    if (hash2[out - 'a']-- <= hash1[out - 'a']) {
        count--;
    }
}

• 当滑动窗口的大小（通过 right - left + 1 计算）大于字符串 p 的长度 m 时，说明窗口已经足够大了，需要尝试收缩窗口（移出左边界的字符）来继续判断后续的子串情况。
• 获取要移出窗口（左边界 left 指向的字符）的字符 out，然后将左边界 left 右移一位（left++），实现窗口收缩。
• 接着对移出窗口的字符在 hash2 数组中的计数减1（hash2[out - 'a']--），并判断减1后的计数是否小于等于该字符在 hash1 数组中的计数，如果是，则说明这个字符的匹配数量减少了，相应地将 count 减1，表示当前窗口内与字符串 p 匹配的字符个数少了一个。

5. 结果更新部分：

if (count == m) {
    ret.add(left);
}

• 当 count 的值等于字符串 p 的长度 m 时，意味着当前滑动窗口内的字符出现频次与字符串 p 中各字符出现频次完全一致，即当前窗口内的子串是字符串 p 的异位词，此时将窗口的左边界索引 left 添加到结果列表 ret 中，记录下这个符合要求的子串起始位置。

6. 最终返回结果：

return ret;

在整个滑动窗口遍历完字符串 s 后，方法最终返回 ret 列表，该列表包含了所有在字符串 ss 中是字符串 pp 的异位词的子串起始索引。

综上所述，这段代码通过巧妙地运用滑动窗口和字符频次统计数组，高效地找出了给定字符串中所有符合要求的异位词子串起始索引，时间复杂度与字符串 s 的长度相关，在遍历过程中进行的操作都是常数级别的，整体时间复杂度为 $O(n)$，其中 n 是字符串 s 的长度。

二、串联所有单词的子串（hard）

2.1 题目链接：

串联所有单词的子串

2.2 题目描述：

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

• 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1：

输入： s = “barfoothefoobarman”, words = [“foo”,“bar”]
输出： [0,9]
解释： 因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 “barfoo” 开始位置是 0。它是 words 中以 [“bar”,“foo”] 顺序排列的连接。
子串 “foobar” 开始位置是 9。它是 words 中以 [“foo”,“bar”] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2：

输入： s = “wordgoodgoodgoodbestword”, words = [“word”,“good”,“best”,“word”]
输出： []
解释： 因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3：

输入： s = “barfoofoobarthefoobarman”, words = [“bar”,“foo”,“the”]
输出： [6,9,12]
解释： 因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 “foobarthe” 开始位置是 6。它是 words 中以 [“foo”,“bar”,“the”] 顺序排列的连接。
子串 “barthefoo” 开始位置是 9。它是 words 中以 [“bar”,“the”,“foo”] 顺序排列的连接。
子串 “thefoobar” 开始位置是 12。它是 words 中以 [“the”,“foo”,“bar”] 顺序排列的连接。

提示：

• 1 <= s.length <= 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• words[i] 和 s 由小写英文字母组成

2.3 题目解析：（超出时间限制）

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class ConcatenationOfAllWordsSubstring {
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if (s == null || words == null || words.length == 0) {
            return result;
        }
        int wordLen = words[0].length();
        int totalLen = wordLen * words.length;
        if (s.length() < totalLen) {
            return result;
        }

        // 用于统计words中各单词出现的频次
        Map<String, Integer> wordMap = new HashMap<>();
        for (String word : words) {
            wordMap.put(word, wordMap.getOrDefault(word, 0) + 1);
        }

        // 从不同起始位置开始遍历（步长为单词长度）
        for (int i = 0; i <= s.length() - totalLen; i++) {
            Map<String, Integer> seenMap = new HashMap<>();
            int j;
            for (j = 0; j < words.length; j++) {
                int index = i + j * wordLen;
                String sub = s.substring(index, index + wordLen);
                if (!wordMap.containsKey(sub)) {
                    break;
                }
                seenMap.put(sub, seenMap.getOrDefault(sub, 0) + 1);
                if (seenMap.get(sub) > wordMap.get(sub)) {
                    break;
                }
            }
            if (j == words.length) {
                result.add(i);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        String s1 = "barfoothefoobarman";
        String[] words1 = {"foo", "bar"};
        System.out.println(findSubstring(s1, words1));

        String s2 = "wordgoodgoodgoodbestword";
        String[] words2 = {"word", "good", "best", "word"};
        System.out.println(findSubstring(s2));

        String s3 = "barfoofoobarthefoobarman";
        String[] words3 = {"bar", "foo", "the"};
        System.out.println(findSubstring(s3, words3));
    }
}

代码解析如下：

2.3.1 整体思路

利用滑动窗口，从字符串 s 的不同起始位置开始，以单词长度为步长，尝试找出长度与所有单词串联起来长度相等的子串，通过哈希表分别统计给定单词数组 words 中单词出现的频次以及在滑动窗口内单词出现的频次，对比两个哈希表来判断当前窗口内的子串是否是由 words 中单词串联而成的。

2.3.2 具体步骤

1. 初始化及边界判断：
   • 创建 result 列表用于存储符合要求的子串起始索引。首先对输入进行合法性判断，如果 s 为空、words 为空或者 words 长度为0，则直接返回空列表。
   • 取出 words 中单词的长度 wordLen，并计算出所有单词串联起来的总长度 totalLen，如果 s 的长度小于 totalLen，说明不可能存在符合要求的串联子串，同样返回空列表。
   • 创建 wordMap 哈希表，遍历 words 数组，统计每个单词在 words 中出现的频次，使用 getOrDefault 方法来处理单词第一次出现的情况，将其频次初始化为1或者在已有频次基础上加1。
2. 滑动窗口遍历及判断：
   • 通过外层 for 循环，从 s 的起始位置开始，以步长为 wordLen 进行遍历，只要当前起始位置加上 totalLen 不超过 s 的长度即可（i <= s.length() - totalLen）。
   • 在内层循环中，针对每个起始位置 i，创建 seenMap 哈希表用于统计当前窗口内各单词出现的频次。通过内层 for 循环遍历 words 数组个数次（j 从0到 words.length - 1），每次获取当前窗口对应位置的子串（通过 s.substring(index, index + wordLen) 获取，其中 index = i + j * wordLen）。
   • 如果获取的子串不在 wordMap 中（即不是 words 中的单词），直接跳出内层循环。如果在，则将其加入 seenMap 并更新其频次，然后判断该单词在 seenMap 中的频次是否大于在 wordMap 中的频次，如果大于，说明当前窗口内该单词出现次数过多，不符合要求，同样跳出内层循环。
3. 结果更新：
   • 当内层循环完整执行完（即 j == words.length），说明当前窗口内的子串是由 words 中单词按某种顺序串联而成的，将当前起始位置 i 添加到 result 列表中。
4. 主函数测试：
   在 main 方法中分别给出了题目示例中的三组测试数据，调用 findSubstring 方法并输出结果，可以验证代码对于不同输入字符串的正确性。

这段代码通过合理运用滑动窗口和哈希表进行频次统计，有效地找出了字符串 s 中所有符合要求的串联子串起始索引，时间复杂度相对较高，主要取决于外层循环遍历 s 的次数以及内层循环遍历 words 数组的次数等操作，整体时间复杂度为 $O(n\times m\times k)$，其中 n 是字符串 s 的长度，m 是 words 数组的长度，k 是单词的长度。不过在实际应用中，对于给定的输入规模限制，该代码不能够在合理时间内完成任务。

2.4 代码优化

public List<Integer> findSubstring(String s, String[] words) {
    List<Integer> ret = new ArrayList<Integer>();
    // 保存字典中所有单词的频次
    Map<String, Integer> hash1 = new HashMap<>();
    for (String str : words) {
        hash1.put(str, hash1.getOrDefault(str, 0) + 1);
    }

    int len = words[0].length(), m = words.length;
    // 执行次数
    for (int i = 0; i < len; i++) {
        // 保存窗⼝内所有单词的频次
        Map<String, Integer> hash2 = new HashMap<>();
        for (int left = i, right = i, count = 0; right + len <= s.length(); right += len) {
            // 进窗⼝ + 维护 count
            String in = s.substring(right, right + len);
            hash2.put(in, hash2.getOrDefault(in, 0) + 1);
            if (hash2.get(in) <= hash1.getOrDefault(in, 0)) {
                count++;
            }
            // 判断
            if (right - left + 1 > len * m) {
                // 出窗⼝ + 维护 count
                String out = s.substring(left, left + len);
                if (hash2.get(out) <= hash1.getOrDefault(out, 0)) {
                    count--;
                }
                hash2.put(out, hash2.get(out) - 1);
                left += len;
            }
            // 更新结果
            if (count == m) {
                ret.add(left);
            }
        }
    }
    return ret;
}

2.4.1 整体功能概述

这段Java代码的功能是在给定的字符串 s 中查找所有能够由字符串数组 words 中单词串联而成的子串起始索引，并将这些索引存放在 List<Integer> 类型的列表 ret 中返回。代码通过滑动窗口的方式，结合使用两个哈希表来分别统计给定单词集合中单词的频次以及滑动窗口内单词的频次，以此判断窗口内的子串是否符合要求。

2.4.2 代码详细解析

1. 初始化部分：

List<Integer> ret = new ArrayList<Integer>();
// 保存字典中所有单词的频次
Map<String, Integer> hash1 = new HashMap<>();
for (String str : words) {
    hash1.put(str, hash1.getOrDefault(str, 0) + 1);
}

int len = words[0].length(), m = words.length;

• 首先创建了一个 ArrayList 类型的列表 ret，用于存储最终找到的符合要求的子串起始索引。
• 接着创建了一个哈希表 hash1，用于统计输入的字符串数组 words 中每个单词出现的频次。通过遍历 words 数组，对于每个单词 str，使用 getOrDefault 方法来处理单词第一次出现的情况，将其频次初始化为1或者在已有频次基础上加1，以此完成对 words 中单词频次的统计。
• 然后获取 words 中每个单词的长度 len（因为题目中限定了 words 中所有单词长度相同）以及单词的个数 m，这两个变量后续会用于判断窗口大小以及循环控制等操作。

2. 多轮滑动窗口循环部分（核心逻辑）：

for (int i = 0; i < len; i++) {
    // 保存窗⼝内所有单词的频次
    Map<String, Integer> hash2 = new HashMap<>();
    for (int left = i, right = i, count = 0; right + len <= s.length(); right += len) {

• 外层的 for 循环以 words 中单词长度 len 为步长进行执行，总共会执行 len 次。这样做的目的是从不同的起始位置开始去尝试寻找符合要求的串联子串，因为子串的起始位置可能在每个单词长度间隔的位置上都有可能出现。

• 针对每一轮（每次外层循环），创建一个新的哈希表 hash2，它用于统计当前滑动窗口内各个单词出现的频次。

• 内层的 for 循环则是真正模拟滑动窗口在字符串 s 上的移动过程，初始化了三个变量：

  • left 表示滑动窗口的左边界，初始值为当前外层循环的起始位置 i，后续会根据窗口收缩等操作进行更新。
  • right 表示滑动窗口的右边界，初始值同样为 i，并且随着循环每次向右移动一个单词的长度（通过 right += len 来实现，同时循环条件 right + len <= s.length() 保证了不会越界，即窗口内始终能获取到完整长度为 len 的子串）。
  • count 用于统计当前滑动窗口内与 words 中单词匹配的个数，初始化为0，后续会根据窗口内单词的进出情况进行相应的增减操作。

3. 窗口内单词进入处理及匹配计数维护：

// 进窗⼝ + 维护 count
String in = s.substring(right, right + len);
hash2.put(in, hash2.getOrDefault(in, 0) + 1);
if (hash2.get(in) <= hash1.getOrDefault(in, 0)) {
    count++;
}

• 当窗口右移（即每次内层循环）时，先获取新进入窗口（通过 right 指针指向的位置获取长度为 len 的子串）的单词 in，这里使用 substring 方法来截取相应的子串。
• 然后将该单词在 hash2 哈希表中对应的计数加1（hash2.put(in, hash2.getOrDefault(in, 0) + 1)），表示这个单词在窗口内出现的次数增加了一次。
• 接着判断增加后的计数是否小于等于该单词在 hash1 哈希表（也就是原始 words 中该单词出现的次数）中的计数，如果是，则说明这个单词的匹配数量增加了，将 count 加1，表示当前窗口内与 words 中单词匹配的个数又多了一个。

4. 窗口大小判断及窗口内单词移出处理和匹配计数维护：

// 判断
if (right - left + 1 > len * m) {
    // 出窗⼝ + 维护 count
    String out = s.substring(left, left + len);
    if (hash2.get(out) <= hash1.getOrDefault(out, 0)) {
        count--;
    }
    hash2.put(out, hash2.get(out) - 1);
    left += len;
}

• 当滑动窗口的大小（通过 right - left + 1 计算）大于所有单词串联起来的总长度（len * m，其中 len 是单个单词长度，m 是单词个数）时，说明窗口已经足够大了，需要尝试收缩窗口（移出左边界的单词）来继续判断后续的子串情况。
• 首先获取要移出窗口（左边界 left 指向的位置获取长度为 len 的子串）的单词 out，然后判断该单词在 hash2 哈希表中的计数减1后是否小于等于其在 hash1 哈希表中的计数，如果是，则说明这个单词的匹配数量减少了，相应地将 count 减1，表示当前窗口内与 words 中单词匹配的个数少了一个。
• 接着将该单词在 hash2 哈希表中的计数减1（hash2.put(out, hash2.get(out) - 1)），并将左边界 left 向右移动一个单词的长度（left += len），实现窗口收缩。

5. 结果更新部分：

// 更新结果
if (count == m) {
    ret.add(left);
}

• 当 count 的值等于 words 中单词的个数 m 时，意味着当前滑动窗口内的单词出现频次与 words 中各单词出现频次完全一致，即当前窗口内的子串是由 words 中单词按某种顺序串联而成的，此时将窗口的左边界索引 left 添加到结果列表 ret 中，记录下这个符合要求的子串起始位置。

6. 最终返回结果：

return ret;

在经过 len 轮滑动窗口遍历完整个字符串 s 后，方法最终返回 ret 列表，该列表包含了所有在字符串 s 中是由 words 中单词串联而成的子串起始索引。

综上所述，这段代码通过巧妙地运用多次滑动窗口（以单词长度为步长）以及利用两个哈希表进行单词频次统计，有效地找出了给定字符串中所有符合要求的串联子串起始索引，时间复杂度方面，由于存在多层循环嵌套，外层循环执行 len 次（len 为单词长度），内层循环与字符串 s 的长度以及 words 中单词个数等相关，整体时间复杂度相对较高，大致为 $O(n\times m\times k)$（其中 n 是字符串 s 的长度，m 是 words 数组的长度，k 是单词的长度），不过在题目给定的输入规模限制下，通常能在合理时间内完成任务。

三、最小覆盖子串（hard）

3.1 题目链接：

最小覆盖子串

3.2 题目描述：

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入： s = “ADOBECODEBANC”, t = “ABC”
输出： "BANC"
解释： 最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。

示例 2：

输入： s = “a”, t = “a”
输出： "a"
解释： 整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = “a”, t = “aa”
输出: ""
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

• m == s.length
• n == t.length
• 1 <= m, n <= 105
• s 和 t 由英文字母组成

3.3 题目解析：

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

public class MinimumWindowSubstring {
    public static String minWindow(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) {
            return "";
        }

        // 用于统计字符串t中各字符出现的频次
        Map<Character, Integer> targetMap = new HashMap<>();
        for (char c : t.toCharArray()) {
            targetMap.put(c, targetMap.getOrDefault(c, 0) + 1);
        }

        // 用于统计滑动窗口内各字符出现的频次
        Map<Character, Integer> windowMap = new HashMap<>();
        int left = 0;
        int minLen = Integer.MAX_VALUE;
        String result = "";
        int matchCount = 0;
        for (int right = 0; right < s.length(); right++) {
            char rightChar = s.charAt(right);
            windowMap.put(rightChar, windowMap.getOrDefault(rightChar, 0) + 1);
            // 避免空指针异常，先判断窗口中字符是否在目标map中存在对应记录，再进行频次比较
            if (targetMap.containsKey(rightChar) && windowMap.get(rightChar).equals(targetMap.get(rightChar))) {
                matchCount++;
            }

            // 当窗口内已匹配的字符数等于t中字符种类数时，尝试收缩窗口
            while (matchCount == targetMap.size() && left <= right) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    result = s.substring(left, right + 1);
                }
                char leftChar = s.charAt(left);
                windowMap.put(leftChar, windowMap.get(leftChar) - 1);
                // 同样避免空指针异常，先判断窗口中字符是否在目标map中存在对应记录，再进行频次相关判断
                if (targetMap.containsKey(leftChar) && windowMap.get(leftChar) < targetMap.get(leftChar)) {
                    matchCount--;
                }
                left++;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        String s1 = "ADOBECODEBANC";
        String t1 = "ABC";
        System.out.println(minWindow(s1, t1));

        String s2 = "a";
        String t2 = "a";
        System.out.println(minWindow(s2, t2));

        String s3 = "a";
        String t3 = "aa";
        System.out.println(minWindow(s3, t3));
    }
}

代码解析如下：

3.3.1 整体思路

利用滑动窗口在字符串 s 上移动，通过两个哈希表分别统计字符串 t 中各字符出现的频次以及滑动窗口内各字符出现的频次。不断调整窗口大小，当窗口内包含了 t 中所有字符且数量也满足要求时，尝试收缩窗口以找到满足条件的最小子串，最终返回这个最小子串。

3.3.2 具体步骤

1. 初始化及边界判断：
   • 首先对输入的字符串 s 和 t 进行合法性判断，如果 s 为 null、t 为 null 或者 s 的长度小于 t 的长度，直接返回空字符串，因为这种情况下不可能存在符合要求的覆盖子串。
   • 创建 targetMap 哈希表，遍历字符串 t，统计 t 中每个字符出现的频次，使用 getOrDefault 方法来处理字符第一次出现的情况，将其频次初始化为1或者在已有频次基础上加1。
   • 创建 windowMap 哈希表，用于后续统计滑动窗口内字符的频次。初始化滑动窗口的左边界 left 为0，最小子串长度 minLen 为 Integer.MAX_VALUE，结果字符串 result 为空字符串，以及用于记录窗口内与 t 中字符匹配的个数的 matchCount 为0。
2. 滑动窗口移动及判断：
   • 通过 for 循环让右边界 right 从0开始不断右移扩大窗口，将新进入窗口的字符加入 windowMap 并更新其频次。如果该字符在 windowMap 中的频次与在 targetMap 中的频次相等，说明该字符的匹配个数增加了，将 matchCount 加1。
   • 当窗口内已匹配的字符数（matchCount）等于 t 中字符种类数（targetMap.size()）时，意味着当前窗口内包含了 t 中所有字符且数量也符合要求，此时尝试收缩窗口以找到最小子串：
     • 先判断当前窗口大小（right - left + 1）是否小于已记录的最小子串长度 minLen，如果是，则更新 minLen 为当前窗口大小，并将 result 更新为当前窗口对应的子串（通过 s.substring(left, right + 1) 获取）。
     • 接着要准备收缩窗口，将左边界 left 对应的字符从窗口移除，先获取该字符，然后将该字符在 windowMap 中的频次减1，如果减1后的频次小于该字符在 targetMap 中的频次，说明移除这个字符后匹配个数会减少，将 matchCount 减1，最后将 left 指针右移一位，实现窗口收缩。
3. 主函数测试：
   在 main 方法中分别给出了题目示例中的三组测试数据，调用 minWindow 方法并输出结果，可以验证代码对于不同输入字符串的正确性。

这段代码通过合理运用滑动窗口和哈希表进行字符频次统计，有效地找出了字符串 s 中涵盖字符串 t 所有字符的最小子串，时间复杂度方面，由于需要遍历字符串 s 一次，在遍历过程中对哈希表的操作时间复杂度通常可看作常数级别，整体时间复杂度为 $O(n)$，其中 n 是字符串 s 的长度。

3.4 代码优化

以下是对给定的minWindow方法代码的详细解析：

3.4.1 整体功能概述

这段Java代码实现了在给定字符串 ss 中查找涵盖另一个字符串 tt 所有字符的最小子串的功能。它通过滑动窗口的方式，结合使用两个长度为128的整数数组（利用ASCII码范围来统计字符频次）来判断窗口内的字符是否满足包含 tt 中所有字符且数量足够的条件，进而不断调整窗口找到最小子串。

3.4.2 代码详细解析

1. 初始化部分：

char[] s = ss.toCharArray();
char[] t = tt.toCharArray();

// 统计字符串 t 中每⼀个字符的频次
int[] hash1 = new int[128];
// 统计有效字符有多少种
int kinds = 0;
for (char ch : t) {
    if (hash1[ch]++ == 0) {
        kinds++;
    }
}
// 统计窗⼝内每个字符的频次
int[] hash2 = new int[128];

int minlen = Integer.MAX_VALUE, begin = -1;

• 首先将输入的字符串 ss 和 tt 分别转换为字符数组 s 和 t，方便后续按字符进行操作。
• 创建 int 类型的数组 hash1，长度为128（因为ASCII码表的范围大致是0 - 127，可用于统计常见字符的频次），用于统计字符串 t 中每个字符出现的次数。通过遍历 t 字符数组，每遇到一个字符 ch，就将 hash1[ch] 的值加1（hash1[ch]++），同时在该字符第一次出现（即 hash1[ch] 原本为0时），将表示字符种类数的变量 kinds 加1，这样就统计出了字符串 t 中不同字符的种类数量。
• 创建同样长度为128的数组 hash2，用于后续统计滑动窗口内各字符出现的频次，初始化为全0。
  • 初始化两个变量：minlen 用于记录找到的满足条件的最小子串长度，初始化为 Integer.MAX_VALUE，表示一个很大的值，方便后续比较更新；begin 用于记录最小子串在原字符串 ss 中的起始位置，初始化为 -1，表示还未找到合适的子串。

2. 滑动窗口循环部分（核心逻辑）：

for (int left = 0, right = 0, count = 0; right < s.length; right++) {

• 这里使用了一个 for 循环来模拟滑动窗口在字符串 s 上的移动，同时初始化了三个变量：
  • left 表示滑动窗口的左边界，初始化为0，后续会根据窗口收缩等操作进行更新。
  • right 表示滑动窗口的右边界，初始化为0，并且随着循环每次向右移动一位（通过 right++，循环条件控制其不会越界）。
  • count 用于统计当前滑动窗口内与字符串 t 中字符匹配的个数，初始化为0，后续会根据窗口内字符的进出情况进行相应的增减操作。

3. 窗口内字符进入处理及匹配计数维护：

char in = s[right];
// 进窗⼝ + 维护 count
if (++hash2[in] == hash1[in]) {
    count++;
}

• 当窗口右移（即每次循环）时，获取新进入窗口（通过 right 指针指向的位置）的字符 in。
• 然后将该字符在 hash2 数组中对应的计数加1（++hash2[in]），表示这个字符在窗口内出现的次数增加了一次。接着判断增加后的计数是否等于该字符在 hash1 数组（也就是字符串 t 中该字符出现的次数）中的计数，如果是，则说明这个字符的匹配数量增加了，将 count 加1，表示当前窗口内与字符串 t 匹配的字符个数又多了一个。

4. 窗口大小判断及窗口内字符移出处理和匹配计数维护：

while (count == kinds) {
    // 更新结果
    if (right - left + 1 < minlen) {
        minlen = right - left + 1;
        begin = left;
    }
    char out = s[left++];
    // 出窗⼝ + 维护 count
    if (hash2[out]-- == hash1[out]) {
        count--;
    }
}

• 当 count（窗口内匹配的字符个数）等于 kinds（字符串 t 中不同字符的种类数）时，意味着当前窗口内包含了 t 中所有字符且数量也符合要求，此时进入这个 while 循环来尝试收缩窗口以找到最小子串。
• 首先判断当前窗口大小（通过 right - left + 1 计算）是否小于已记录的最小子串长度 minlen，如果是，则更新 minlen 为当前窗口大小，并将 begin 更新为当前窗口的左边界 left，记录下当前更优的子串起始位置和长度信息。
• 接着要准备收缩窗口，获取要移出窗口（左边界 left 指向的字符）的字符 out，然后将左边界 left 右移一位（left++），实现窗口收缩。
• 对移出窗口的字符在 hash2 数组中的计数减1（hash2[out]--），并判断减1后的计数是否等于该字符在 hash1 数组中的计数，如果是，则说明这个字符的匹配数量减少了，相应地将 count 减1，表示当前窗口内与字符串 t 匹配的字符个数少了一个。

5. 最终结果返回部分：

if (begin == -1) {
    return new String();
} else {
    return ss.substring(begin, begin + minlen);
}

• 最后根据 begin 的值来判断是否找到了满足条件的子串，如果 begin 还是初始值 -1，说明没有找到涵盖 tt 所有字符的子串，就返回一个空字符串；否则，通过 ss.substring(begin, begin + minlen) 截取原字符串 ss 中从 begin 位置开始，长度为 minlen 的子串作为结果返回，这个子串就是涵盖 tt 所有字符的最小子串。

综上所述，这段代码通过巧妙地运用滑动窗口以及基于字符频次统计数组的方式，高效地找出了给定字符串 ss 中涵盖字符串 tt 所有字符的最小子串，时间复杂度与字符串 s 的长度相关，在遍历过程中进行的操作都是常数级别的，整体时间复杂度为 $O(n)$，其中 n 是字符串 s （也就是原 ss 转换后的字符数组）的长度。

四、二分查找（easy）

4.1 题目链接：

二分查找

4.2 题目描述：

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000] 之间。
3. nums 的每个元素都将在 [-9999, 9999] 之间。

4.3 题目解析：

以下是使用Java语言实现的二分查找算法代码，用于解决LeetCode 704题的要求，代码如下：

public class BinarySearch {
    public static int search(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 {
                right = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums1 = {-1, 0, 3, 5, 9, 12};
        int target1 = 9;
        System.out.println(search(nums1, target1));

        int[] nums2 = {-1, 0, 3, 5, 9, 12};
        int target2 = 2;
        System.out.println(search(nums2, target2));
    }
}

代码解析如下：

4.3.1 整体思路

二分查找算法利用了数组是有序的这一特性，通过不断缩小查找区间来定位目标元素。每次取查找区间的中间元素与目标值进行比较，如果相等则找到目标，返回其下标；如果中间元素小于目标值，则说明目标值在中间元素的右侧，更新查找区间的左边界为中间元素的下一个位置；如果中间元素大于目标值，则说明目标值在中间元素的左侧，更新查找区间的右边界为中间元素的上一个位置，如此反复，直到找到目标值或者查找区间为空（即左边界大于右边界）。

4.3.2 具体步骤

1. 初始化查找区间：

int left = 0;
int right = nums.length - 1;

定义两个变量 left 和 right 分别表示查找区间的左边界和右边界，初始时左边界 left 设为0，对应数组的第一个元素下标，右边界 right 设为 nums.length - 1，对应数组的最后一个元素下标，意味着初始查找区间是整个数组。

2. 循环查找：

while (left <= right) {

使用 while 循环来进行查找，只要左边界 left 小于等于右边界 right，就说明查找区间内还有元素，需要继续查找。

3. 计算中间元素下标并比较：

int mid = left + (right - left) / 2;
if (nums[mid] == target) {
    return mid;
} else if (nums[mid] < target) {
    left = mid + 1;
} else {
    right = mid - 1;
}

• 首先计算中间元素的下标 mid，这里使用 left + (right - left) / 2 的方式计算是为了避免直接使用 (left + right) / 2 在 left 和 right 数值较大时可能出现的整数溢出问题。
• 然后将中间元素 nums[mid] 与目标值 target 进行比较：
  • 如果 nums[mid] 等于 target，说明找到了目标元素，直接返回其下标 mid。
  • 如果 nums[mid] 小于 target，说明目标元素在中间元素的右侧，所以将查找区间的左边界 left 更新为 mid + 1，缩小查找区间到中间元素的右侧部分。
  • 如果 nums[mid] 大于 target，说明目标元素在中间元素的左侧，所以将查找区间的右边界 right 更新为 mid - 1，缩小查找区间到中间元素的左侧部分。

4. 未找到目标值的情况：
   当循环结束（即 left > right）时，说明整个数组都已经查找完了，仍然没有找到目标值，此时按照题目要求返回 -1，表示目标值不存在于给定的数组中。

5. 主函数测试：
   在 main 方法中分别给出了题目示例中的两组测试数据，调用 search 方法并输出结果，可以验证代码对于不同输入数组和目标值的正确性。

二分查找算法的时间复杂度为 $O(\log n)$，其中 n 是数组 nums 的长度，因为每次循环都会将查找区间缩小一半；空间复杂度为 $O(1)$，因为只使用了有限的几个变量，没有随输入规模增长而额外占用大量空间。

4.4 朴素二分查找的细节问题

以下是对朴素二分查找相关细节问题的分析回答：

4.4.1 循环结束条件

在朴素二分查找的代码中，常见的循环结束条件是 while (left <= right)，下面详细解释其原因：

• 区间表示与搜索范围：
  我们通过两个指针 left 和 right 来界定搜索区间。初始时，left 指向数组的第一个元素下标（通常为0），right 指向数组的最后一个元素下标（即 nums.length - 1），整个区间 [left, right] 代表了所有可能包含目标元素的范围。

• 持续搜索的依据：
  只要 left <= right，就意味着搜索区间内还有元素未被检查完，还有可能存在目标元素。例如，当 left 和 right 相等时，说明此时搜索区间只剩下一个元素了，仍需要进行比较判断这个元素是否就是目标元素，所以这个条件下循环要继续执行。

• 结束搜索的情况：
  当 left 大于 right 时，搜索区间 [left, right] 就变为空了，也就是已经遍历完了所有可能包含目标元素的位置，都没有找到目标元素，此时循环结束，按照二分查找的逻辑返回 -1，表示目标元素不存在于数组中。

4.4.2 二分查找的算法为什么是正确的？

二分查找算法正确的原因主要基于以下几点：

• 有序性前提：
  二分查找要求输入的数组是有序的（本题中为升序排列），这是算法正确性的基础。因为基于有序的特性，我们才能通过比较中间元素与目标元素的大小关系，合理地缩小搜索区间，确定目标元素可能存在的范围。

• 每次缩小范围的合理性：
  在每次循环中，我们计算中间元素 nums[mid] 并与目标值 target 进行比较：

  • 如果 nums[mid] 等于 target，直接找到了目标元素，这显然是正确的返回结果。
  • 如果 nums[mid] 小于 target，由于数组是升序的，所以目标元素必然在中间元素 nums[mid] 的右侧区间（即更大的元素所在区间），所以我们将搜索区间的左边界 left 更新为 mid + 1，这样就合理地排除了中间元素及其左侧不可能包含目标元素的部分，缩小了搜索范围，且保证目标元素如果存在，一定还在新的搜索区间内。
  • 同理，当 nums[mid] 大于 target 时，目标元素必然在中间元素的左侧区间（即更小的元素所在区间），将搜索区间的右边界 right 更新为 mid - 1，同样合理地排除了部分不可能包含目标元素的区间，缩小了范围且目标元素如果存在仍在新区间内。

• 最终收敛性：
  随着不断地循环比较和区间缩小，搜索区间会越来越小，最终要么找到目标元素并返回其下标（在 nums[mid] 等于 target 时），要么搜索区间变为空（left > right），表示已经遍历完所有可能位置但未找到目标元素，返回 -1。整个过程通过不断合理地缩小范围并保证不会遗漏目标元素所在区间，所以算法是正确的，可以准确判断目标元素是否存在于有序数组中并返回其下标（若存在）。

4.4.3 时间复杂度分析

二分查找的时间复杂度为 $O(\log n)$，分析如下：

• 每次操作对区间的影响：
  在每一次循环迭代过程中，我们都会将当前的搜索区间缩小一半。例如，第一次循环时搜索区间长度为 n（数组长度），经过一次比较和区间更新后，下一次循环的搜索区间长度大致变为 n/2（如果是平均情况），再下一次就变为 n/4，以此类推。

• 计算迭代次数与输入规模的关系：
  假设经过 k 次迭代后搜索区间缩小到只剩下一个元素或者变为空区间（即循环结束），那么就有 $n\times (\frac{1}{2}{)}^k\le 1$（这里的不等式表示经过 k 次每次减半的操作后，区间长度最多变为1或者更小，意味着已经完成了搜索）。对这个不等式进行求解可得：
  $$\begin{array}{rl}(\frac{1}{2}{)}^k& \le \frac{1}{n}\\ 2^k& \ge n\\ k& \ge {\log }_{2}n\end{array}$$

也就是说，最多经过大约 ${\log }_{2}n$ 次循环迭代就能完成整个查找过程，这里的 n 是数组 nums 的长度。

• 时间复杂度表示：
  由于循环迭代的次数与数组长度 n 的对数关系，在大O表示法下，我们忽略常数系数（对数的底数），所以二分查找算法的时间复杂度表示为 $O(\log n)$。这意味着随着数组长度 n 的增加，查找所需的时间增长速度相对较慢，体现了二分查找在有序数组中查找元素的高效性。

综上所述，二分查找通过合理的循环结束条件、基于有序数组特性保证算法正确性，并有着高效的 $O(\log n)$ 时间复杂度，使其成为在有序数据结构中查找元素的常用算法。

五、在排序数组中查找元素的第一个和最后一个位置（medium）

5.1 题目链接：

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

5.2 题目描述：

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入： nums = [5,7,7,8,8,10], target = 8
输出： [3,4]

示例 2：

输入： nums = [5,7,7,8,8,10], target = 6
输出： [-1,-1]

示例 3：

输入： nums = [], target = 0
输出： [-1,-1]

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums 是一个非递减数组
• -109 <= target <= 109

5.3 题目解析：

public class SearchRange {
    public static int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        if (nums == null || nums.length == 0) {
            return result;
        }

        // 第一次二分查找，找起始位置（左边界）
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (nums[left] == target) {
            result[0] = left;
        } else {
            return result;
        }

        // 第二次二分查找，找结束位置（右边界），重置右边界
        right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        result[1] = right;
        return result;
    }

    public static void main(String[] args) {
        int[] nums1 = {5, 7, 7, 8, 8, 10};
        int target1 = 8;
        System.out.println(Arrays.toString(searchRange(nums1, target1)));

        int[] nums2 = {5, 7, 7, 8, 8, 10};
        int target2 = 6;
        System.out.println(Arrays.toString(searchRange(nums2, target2)));

        int[] nums3 = {};
        int target3 = 0;
        System.out.println(Arrays.toString(searchRange(nums3, target3)));
    }
}

代码解析如下：

5.3.1 整体思路

利用二分查找的思想，由于数组是非递减顺序排列的，通过两次二分查找分别确定目标值在数组中的起始位置（左边界）和结束位置（右边界）。第一次二分查找尽量让中间值 mid 偏向左边，找到左边界；第二次二分查找尽量让中间值 mid 偏向右边，找到右边界。

5.3.2 具体步骤

1. 初始化及边界判断：

int[] result = {-1, -1};
if (nums == null || nums.length == 0) {
    return result;
}

首先创建一个长度为2的数组 result，用于存储最终要返回的目标值的起始位置和结束位置，初始化为 [-1, -1]，表示默认未找到目标值的情况。然后对输入的数组 nums 进行合法性判断，如果数组为 null 或者长度为0，直接返回 result，因为这种情况下不存在目标值在数组中的位置信息。

2. 第一次二分查找（找起始位置 - 左边界）：

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

• 初始化左右指针 left 和 right，分别指向数组的第一个元素和最后一个元素，界定搜索区间。
• 在 while 循环中，通过计算中间元素 mid（使用 left + (right - left) / 2 避免整数溢出）与目标值 target 进行比较：
  • 如果 nums[mid] 小于 target，说明目标值在中间元素的右侧，所以更新左指针 left 为 mid + 1，缩小搜索区间到中间元素的右侧部分。
  • 如果 nums[mid] 大于等于 target，说明目标值在中间元素或者其左侧，为了找到最左边的目标值位置，将右指针 right 更新为 mid，让搜索区间继续向左边缩小。
• 循环结束后（此时 left 和 right 相等），判断 nums[left] 是否等于目标值 target，如果相等，说明找到了目标值的起始位置，将其赋值给 result[0]；否则，直接返回 result，表示数组中不存在目标值。

3. 第二次二分查找（找结束位置 - 右边界）：

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

• 首先将右指针 right 重置为数组的最后一个元素下标，因为要重新开始查找目标值的右边界，界定新的搜索区间。
• 同样通过 while 循环进行二分查找，不过这次计算中间元素 mid 时使用 left + (right - left + 1) / 2 的方式，这样可以让 mid 在取整时更偏向右边，有助于找到右边界：
  • 如果 nums[mid] 大于 target，说明目标值在中间元素的左侧，更新右指针 right 为 mid - 1，缩小搜索区间到中间元素的左侧部分。
  • 如果 nums[mid] 小于等于 target，说明目标值在中间元素或者其右侧，为了找到最右边的目标值位置，将左指针 left 更新为 mid，让搜索区间继续向右边缩小。
• 循环结束后（此时 left 和 right 相等），将右指针 right 的值赋值给 result[1]，作为目标值的结束位置，最后返回 result 数组，其存储了目标值在数组中的起始位置和结束位置（如果存在的话），若不存在则仍为初始的 [-1, -1]。

4. 主函数测试：
   在 main 方法中分别给出了题目示例中的三组测试数据，调用 searchRange 方法并输出结果，可以验证代码对于不同输入数组和目标值的正确性。

通过两次二分查找，每次查找过程中都将搜索区间不断缩小，且每次操作的时间复杂度都是 $O(\log n)$，所以整个算法解决此问题的时间复杂度依然为 $O(\log n)$，符合题目要求，能高效地在排序数组中查找目标值的起始和结束位置。

以下是对查找区间左端点和右端点相关细节问题更为细致全面的分析：

5.4 查找区间左端点的细节问题

5.4.1 循环条件

• 区间范围与持续搜索判定：
  在查找目标值在排序数组中的左端点（起始位置）时，通常采用 while (left < right) 作为循环条件。这里 left 和 right 分别代表搜索区间的左右边界，初始状态下，left 指向数组的第一个元素下标（一般为 0），right 指向数组的最后一个元素下标（即 nums.length - 1），整个区间 [left, right] 涵盖了所有可能包含目标值起始位置的范围。

循环持续进行的依据就是 left 小于 right，这意味着搜索区间内还有不止一个元素，还需要进一步通过比较中间元素与目标值的关系来缩小范围，以精准定位到目标值首次出现的位置。只要这个区间内还有多个元素，就需要不断迭代循环去判断，逐步排除不可能的部分，向目标值的左端点靠近。

例如，给定数组 [2, 3, 5, 5, 7] 去查找目标值 5 的左端点，一开始搜索区间是整个数组范围，随着循环一次次执行，区间不断缩小，最终确定出 5 第一次出现的准确位置所在的最小区间（即 left 和 right 相等时的那个位置）。

• 避免死循环机制：
  之所以选择 left < right 而不是 left <= right，关键在于区间更新的策略与避免死循环的考量。在循环体内部，依据中间元素 nums[mid] 和目标值 target 的比较结果来更新区间：
  • 当 nums[mid] < target 时，表明目标值在中间元素的右侧，所以将 left 更新为 mid + 1，这样就把搜索区间缩小到了中间元素的右侧部分，使得区间严格变小，朝着目标值所在方向移动。
  • 当 nums[mid] >= target 时，意味着目标值可能就在中间元素或者其左侧，为了找到最左边的目标值出现位置，把 right 更新为 mid，使得区间往左边缩小。

无论哪种情况，每次循环都会使搜索区间严格变小，不会出现 left 和 right 指针保持不变、导致循环无法终止的死循环情况。这样，循环最终一定会因为 left 和 right 相等而结束，顺利进入下一步的判断流程。

• 与后续判断的协同作用：
  当循环结束，也就是 left 和 right 相等时，此时搜索区间已经缩小到只剩一个元素了。接下来就需要判断这个唯一元素（通过 nums[left] 或者 nums[right]，二者此时指向同一个元素）是否等于目标值 target。如果相等，那就成功找到了目标值的起始位置（左端点），可以将其记录下来；要是不相等，那就说明数组中实际上不存在目标值，按照题目设定返回表示未找到的相应结果（比如 [-1, -1]）。这种循环条件和后续判断环节紧密配合，确保了整个查找左端点过程的准确性和完整性。

5.4.2 求中间元素的操作

• 防止整数溢出考量：
  在计算中间元素下标时，通常采用 int mid = left + (right - left) / 2 的方式。这主要是为了避免整数溢出的问题。在一些情况下，如果简单地使用 (left + right) / 2 来计算中间元素下标，当 left 和 right 所代表的下标值较大时（比如在处理较长数组，且它们接近 Integer.MAX_VALUE 时），直接相加操作可能会导致整数溢出，从而得出错误的中间元素下标，进而影响整个查找过程的正确性。

而采用 left + (right - left) / 2 的计算方式，先是计算 right - left 的差值，这个差值在正常的数组下标范围内通常是不会溢出的，然后将其除以 2 得到中间位置相对于 left 的偏移量，最后再与 left 相加，就可以安全且准确地获取到中间元素的下标，保证了算法在面对各种规模数组时都能稳定运行，不会因为数值溢出问题而出现错误。

• 偏向左侧取整的特性及作用：
  这种计算方式得到的中间元素下标 mid 在取整时有偏向左侧的特性。例如，当 left = 0，right = 1 时，按照此公式计算得到的 mid = 0。在查找目标值左端点的情境下，这种偏向左侧取整的特点是非常契合查找逻辑的。

因为我们的目标是找到目标值在数组中首次出现的位置，也就是最左边的位置。当遇到 nums[mid] 等于目标值 target 时，通过将 right 更新为 mid（如前面循环条件部分所述的区间更新策略），可以继续让搜索区间往左边缩小，进一步去探寻是否还有更靠左的目标值出现位置。所以这种偏向左侧取整的中间元素计算方式有助于精准地定位到目标值的左端点，符合整个查找起始位置的算法设计意图。

5.5 查找区间右端点的细节问题

5.5.1 循环条件

• 界定搜索区间与循环持续依据：
  同样，在查找目标值在排序数组中的右端点（结束位置）时，也常采用 while (left < right) 作为循环条件。这里 left 和 right 依旧是用于界定搜索区间的左右边界，初始时涵盖了整个数组范围，随着循环推进来逐步缩小这个区间，以确定目标值最后出现的位置。

只要 left 小于 right，就表明搜索区间内还有多于一个元素，还需要依据中间元素与目标值的比较情况来进一步缩小范围，不断逼近目标值的右端点。例如，对于数组 [1, 3, 3, 5, 7] 查找目标值 3 的右端点，一开始整个数组都在搜索区间内，随着循环的迭代，区间逐步变小，直至最终确定出 3 最后一次出现的那个最小区间（即 left 和 right 相等时的位置）。

• 避免区间停滞与死循环保障：
  选择 while (left < right) 配合相应的区间更新操作，能有效避免陷入死循环。在循环中，根据中间元素 nums[mid] 和目标值 target 的比较结果对区间进行调整：
  • 当 nums[mid] > target 时，可知目标值在中间元素的左侧，所以将 right 更新为 mid - 1，这样就把搜索区间缩小到了中间元素的左侧部分，保证了区间在朝着目标值的方向合理缩小，不会出现区间停滞不前的情况。
  • 当 nums[mid] <= target 时，意味着目标值可能在中间元素或者其右侧，为了找到目标值最后出现的位置，也就是最靠右的位置，将 left 更新为 mid，使得搜索区间往右侧缩小，持续向目标值的右端点逼近。

通过这样的区间更新策略，每次循环都会使搜索区间严格变小，确保了循环最终会因为 left 和 right 相等而终止，避免了因为区间无法继续缩小而产生死循环的问题，为准确找到目标值的右端点提供了可靠的循环控制机制。

• 与最终判断的有效衔接：
  当循环结束，即 left 和 right 相等时，此时搜索区间缩小到只剩一个元素了。此时需要判断这个元素（通过 nums[left] 或者 nums[right]，二者此时是同一个元素）是否等于目标值 target。若相等，就表明找到了目标值的结束位置（右端点），可以按照要求记录并返回相应结果；若不相等，则意味着数组中不存在目标值，返回表示未找到的特定结果（如 [-1, -1]）。这种循环条件与最终判断环节相互配合，保证了整个查找右端点过程能够准确判断目标值是否存在以及准确获取其结束位置。

5.5.2 求中间元素的操作

• 整数溢出防范与计算原理：
  在查找右端点的二分查找过程中，计算中间元素通常采用 int mid = left + (right - left + 1) / 2 的方式。与查找左端点时防止整数溢出的思路类似，这样做主要是为了避免在计算中间元素下标时出现整数溢出的情况。

使用常规的 (left + right) / 2 计算方式，在 left 和 right 取值较大时，相加操作容易导致溢出错误。而通过先计算 right - left + 1 的值（这个操作在正常的数组下标范围内一般是安全的，不会产生溢出），再将其除以 2 取整，最后与 left 相加来得到中间元素下标，就可以有效规避整数溢出风险，确保在任何合法的数组规模下都能准确无误地计算出中间元素的下标位置，为后续正确判断和缩小区间奠定基础。

• 偏向右侧取整的特性及对查找的助力：
  这种计算方式使得得到的中间元素下标 mid 在取整时具有偏向右侧的特性。例如，当 left = 0，right = 1 时，按照此公式计算得到的 mid = 1。

在查找目标值右端点的场景中，这种偏向右侧取整的特点起着关键作用。当我们比较中间元素 nums[mid] 和目标值 target 时：
- 如果 nums[mid] > target，表明目标值在中间元素的左侧，那么将 right 更新为 mid - 1，把搜索区间缩小到中间元素的左侧，继续往左边去探寻目标值的右端点所在区间。
- 如果 nums[mid] <= target，意味着目标值在中间元素或者其右侧，为了找到目标值最后出现的位置，也就是最靠右的位置，将 left 更新为 mid，使得搜索区间向右侧进一步缩小，不断朝着目标值真正的右端点逼近。

所以，偏向右侧取整的中间元素计算方式与查找右端点的逻辑需求相契合，有助于精准且高效地找到目标值在数组中的结束位置，保障了整个查找算法在查找目标值区间右端点时的准确性和有效性，使其能够在符合要求的 $O(\log n)$ 时间复杂度内完成查找任务。