力扣刷题日常(3-4)

第三题: 无重复字符的最长子串(难度: 中等)

原题:

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

示例 1:

1
2
3

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3.

示例 2:

1
2
3

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1.

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3.
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串.

提示:

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

开始解题:

方法一: 暴力求解

那么看到这个题目的那一刻,我脑袋里的第一反应是暴力求法—把所有可能的子串都找出来,然后一个个检查它们是否含有重复字符,最后记录下最长的那个无重复子串的长度.

比如对于 s = "abcabcbb":

“a” (无重复, 长度1)
“ab” (无重复, 长度 2)
“abc” (无重复, 长度 3)
“abca” (有重复 ‘a’, 无效)
…
“b” (从第二个字符开始,无重复, 长度 1)
“bc” (无重复, 长度 2)
“bca” (无重复, 长度 3)
“bcab” (有重复 ‘b’, 无效)
…

这个方法固然是可行的,但效率异常低下,如果字符串很长,那子串数量会爆发式增长,我们的计算量会变得格外大.

方法二: 滑动窗口

既然我们的暴力求解太慢,那我们来想象一个"窗口",这个窗口在字符串上从左到右滑动.我们始终保持在这个窗口内的所有字符都是不重复的.

那这个"窗口"就是我们的"子串",我们现在要做的就是:

不断尝试扩大这个窗口的右边界,把新的字符包含进来.
如果新进来的字符在窗口内没有重复,那就代表我们的无重复字串又变长了一点.我们记录下现在的长度,和之前记录的最大长度进行对比,看哪个更大.
如果新进来的字符在窗口内已经存在了,说明窗口内的字串不满足"无重复"的条件了,那我们就必须收缩窗口的左边界,知道把那个重复的旧字符"挤"出窗口为止.

这样,我们的窗口就在字符串上"滑动"了起来: 右边界一直向右移动,左边界在必要时也向右移动,这个过程中,窗口的最大尺寸就是我们要求的答案.

这个就是"滑动窗口"算法思想

思路讲完了,接下来讲的就是实现了:

我们需要几个工具

两个指针: 一个 left 指针标记窗口的左边界, 一个 right 指针标记窗口的右边界.
一个"账本": 我们需要一个能快速查询"某个字符是否已在当前窗口内"以及"它在哪个位置"的工具.在C#中, Dictionary<char,.int>(字典,也叫哈希表)是完美的选择.
- Key: 存储字符 char
- Value: 存储该字符最近一次出现时的索引 int

逻辑步骤拆解(以 s = "pwwkew"为例):

初始化:
- left = 0 (窗口左边界)
- maxLength = 0 (记录最大长度)
- charIndexMap = new Dictionary<char, int>() (我们的“账本”)
开始滑动 (用 right 指针从 0 遍历到字符串末尾):

right = 0, 字符是 'p'
- 账本里没有 'p'.
- 把它加入账本: charIndexMap['p'] = 0.
- 当前窗口是 “p”,长度为 0 - 0 + 1 = 1.
- 更新 maxLength = 1.
right = 1, 字符是 'w'
- 账本里没有 'w'.
- 加入账本: charIndexMap['w'] = 1.
- 当前窗口是 “pw”,长度为 1 - 0 + 1 = 2.
- 更新 maxLength = 2.
right = 2, 字符是 'w'
- 冲突！ 账本里已经有 'w' 了,它上次出现的位置是 1.
- 这意味着我们的窗口 [left, right] (即从索引0到2,“pww”) 包含了重复字符.
- 我们必须移动左边界 left.移动到哪里呢？应该移动到重复字符 'w' 上次出现位置的下一个位置.
- 所以,left 更新为 1 + 1 = 2.
- 现在窗口的起始点是索引 2.
- 更新账本里 'w' 的位置: charIndexMap['w'] = 2.
- 当前窗口是 “w” (从索引2到2),长度为 2 - 2 + 1 = 1.maxLength 仍然是 2.
right = 3, 字符是 'k'
- 账本里没有 'k' (注意:此时我们的有效窗口是从 left=2 开始的,所以之前的’p’和第一个’w’已经不算在内了).
- 加入账本: charIndexMap['k'] = 3.
- 当前窗口是 “wk”,长度为 3 - 2 + 1 = 2.maxLength 仍然是 2.
right = 4, 字符是 'e'
- 账本里没有 'e'.
- 加入账本: charIndexMap['e'] = 4.
- 当前窗口是 “wke”,长度为 4 - 2 + 1 = 3.
- 更新 maxLength = 3.
right = 5, 字符是 'w'
- 冲突！ 账本里有 'w',它上次出现的位置是 2.
- 当前 left 是 2.重复字符的位置 2 没有比 left 小,所以这个重复是在我们当前窗口内的.
- 移动左边界 left 到重复字符 'w' 上次位置的下一个位置.
- left 更新为 2 + 1 = 3.
- 更新账本里 'w' 的位置: charIndexMap['w'] = 5.
- 当前窗口是 “kew” (从索引3到5),长度为 5 - 3 + 1 = 3.maxLength 仍然是 3.

循环结束.返回 maxLength,最终结果是 3.

那么这个算法的核心优势在于,我们只遍历了字符串一次,所以它的效率非常高.

比喻解释:

上面的滑动窗口可能还是有些难以理解,我们来做个比喻吧

想象我们有一个传送带,上面按顺序放着字符串 s = "abcabcbb" 的每个字符.我们有一个篮子（就是我们的“窗口”）,我们的任务是用这个篮子从传送带上尽可能多地连续装走字符,但篮子里绝对不能出现两个一样的字符.

开始阶段:
- 传送带过来 'a',我们把它放进篮子.篮子:{'a'}.长度1.
- 传送带过来 'b',篮子里没有,我们放进去.篮子:{'a', 'b'}.长度2.
- 传送带过来 'c',篮子里没有,我们放进去.篮子:{'a', 'b', 'c'}.长度3.这是目前为止我们装到的最长记录.
冲突发生:
- 现在,传送带过来了下一个字符:'a'.
- 我们检查篮子,发现里面已经有一个 'a' 了！
- 根据规则（篮子里不能有重复）,我们不能把这个新的 'a' 直接放进去.我们当前的篮子 {'a', 'b', 'c'} 已经满了（就这个新’a’而言）.
如何解决冲突？:
- 我们的目标是继续从传送带上拿东西,并且要包含这个新的 'a'.
- 为了能把新的 'a' 放进来,我们必须先把篮子里那个旧的 'a' 扔掉.
- 但是,我们不能只扔掉旧的 'a',因为我们必须保持篮子里的东西是连续从传送带上拿的.旧的 'a' 是我们拿的第一个东西.为了扔掉它,我们必须把我们从它开始拿的所有东西都按顺序扔掉,直到它被扔出去为止.
- 所以,我们扔掉旧 'a'.为了保持连续性,我们其实是把我们的“起始点”（也就是 left 指针）移动到了旧 'a' 的下一个位置.
- 操作前:篮子对应子串 "abc" (起始点 left=0)
- 操作后:我们把旧 'a' 扔了,篮子的起始点变成了 'b' (起始点 left=1).现在篮子里是 {'b', 'c'}.
- 现在篮子里没有 'a' 了,我们可以把传送带上那个新的 'a' 放进来了.
- 最终,篮子变成了 {'b', 'c', 'a'}.它对应子串 "bca".这是一个合法的、无重复的子串.

简单一个总结:

收缩左边界（left 指针右移）的目的,就是为了修复窗口的合法性.

当右指针 right 引入一个重复字符时,窗口 [left, right] 就变得不合法了.为了让它重新合法,我们必须从左边移除字符,直到把那个造成重复的“元凶”（旧的那个重复字符）移除出去为止.这样,窗口就又变回了一个不含重复字符的子串,我们就可以继续尝试向右扩大窗口,寻找更长的可能性了.

如果不收缩左边界,那么从当前这个 right 指针开始,无论它再往右走多远,形成的子串 [left, right], [left, right+1], … 都将永远包含那个重复,永远不合法,也就失去了继续计算的意义.

解法代码:

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        // 处理边界情况
        if (string.IsNullOrEmpty(s)) {
            return 0;
        }
 
        // 初始化变量
        // key: 字符, value: 该字符最近一次出现的索引
        var charIndexMap = new Dictionary<char, int>(); 
        int maxLength = 0;
        int left = 0; // 滑动窗口的左边界
 
        // 开始滑动窗口
        for (int right = 0; right < s.Length; right++) {
            char currentChar = s[right];
 
            // 检查是否出现重复,并且重复的字符在当前窗口内
            if (charIndexMap.ContainsKey(currentChar)) {
                // 更新左边界 left
                // Math.Max确保 left 指针不会向左回退
                left = Math.Max(left, charIndexMap[currentChar] + 1);
            }
 
            // 更新（或添加）当前字符的最新位置
            charIndexMap[currentChar] = right;
 
            // 计算当前窗口的长度,并尝试更新最大长度
            maxLength = Math.Max(maxLength, right - left + 1);
        }
 
        return maxLength;
    }
}

知识点解析:

string.IsNullOrEmpty(s)
- 讲解: 这是一个非常实用的静态方法,用于检查一个字符串是否为 null 或者是否为空字符串 "".在编写健壮的代码时,这是一个很好的习惯,可以避免因为传入了 null 而导致程序在后续操作（如 s.Length）中抛出 NullReferenceException.
charIndexMap[currentChar] = right;

讲解: 这是 Dictionary 的索引器用法,非常灵活.
- 如果键 currentChar 已经存在,这行代码会更新该键对应的值为新的 right.
- 如果键 currentChar 不存在,这行代码会添加一个新的键值对到字典中.
在我们的代码里,它完美地实现了“更新字符最新位置”的需求.

滑动窗口思想 (The Sliding Window Pattern)

核心: 这是一种用于解决数组/字符串子区间问题的强大算法模型.它使用两个指针（left, right）来定义一个“窗口”,通过移动这两个指针来“滑动”并处理窗口内的数据.
本质: 它将一些问题的嵌套循环（暴力解法,如O(n²)）优化为单次遍历（O(n)）,通过巧妙地维护窗口状态,避免了大量重复计算.

哈希表/字典的妙用 (The Power of Hash Maps / Dictionaries)

核心: 当我们需要快速地“检查一个元素是否存在”或者“查找一个元素的关联信息”时,Dictionary (哈希表) 应该是我们的首选工具.
优势: 它提供了平均O(1)时间复杂度的插入、删除和查找操作,性能极高.在算法题中,它是优化时间复杂度的关键先生.

空间换时间 (Space-for-Time Tradeoff)

核心: 这是一个经典的计算机科学概念.在我们的解法中,我们额外使用了一个Dictionary来存储信息（占用了空间）,但正是这个额外的空间,让我们算法的执行时间从O(n²)或更高降低到了O(n).在很多场景下,用可接受的内存增长来换取巨大的性能提升是非常值得的.

编写健壮的代码 (Writing Robust Code)

核心: 在函数或方法的开头,优先处理“边缘情况”（Edge Cases）,比如输入为null、空字符串、空集合等.这能让我们的代码更加稳定,避免在后续逻辑中出现意外的运行时错误（如NullReferenceException）.

额外练习题:

选择题

在解决“求满足某条件的连续子数组/子串”问题时,以下哪种算法思想通常是最高效的选择？
A. 递归 (Recursion)
B. 暴力枚举 (Brute Force)
C. 滑动窗口 (Sliding Window)
D. 排序 (Sorting)
在“无重复字符的最长子串”算法中,使用 Dictionary<char, int> 的主要目的是什么？
A. 按字母顺序存储字符.
B. 统计每个字符出现的总次数.
C. 快速判断一个字符是否在当前窗口内,并获取其位置.
D. 减少代码行数.
我们实现的滑动窗口解法的时间复杂度是多少？（n是字符串的长度）
A. O(1) - 常数时间
B. O(log n) - 对数时间
C. O(n) - 线性时间
D. O(n²) - 平方时间

简答题

除了“无重复字符的最长子串”,请你设想一个在游戏开发中可能用得上“滑动窗口”思想的场景.
在我们的代码中,更新左边界的代码是 left = Math.Max(left, charIndexMap[currentChar] + 1);.为什么不直接写成 left = charIndexMap[currentChar] + 1;？请用字符串 "abba" 作为例子来解释.

参考答案

选择题答案:

C. 滑动窗口是专门用来高效处理连续子数组/子串问题的.
C. Dictionary 的O(1)查找特性是算法高效的关键,它让我们能瞬间知道新字符是否与窗口内的字符重复.
C. right 指针和 left 指针都只从左到右遍历字符串一次,所以总的时间复杂度是线性的 O(n).

简答题答案:

场景示例:
- 分析玩家操作: 统计玩家在任意连续的5秒内,点击鼠标或敲击键盘的最高频率（APM - Actions Per Minute）,用于判断玩家是否处于“高能”操作状态.
- 伤害统计: 计算一个持续性伤害技能（如毒雾、火焰地板）在任意3秒内对敌人造成的最大总伤害.
- 资源采集监控: 在一个资源点,判断最近采集的10个资源中,稀有资源的占比是否超过了某个阈值.
原因解释:
使用 Math.Max 是为了防止 left 指针向左回退.left 应该只增不减,代表窗口的起始点只能向前移动.

以 "abba" 为例:
- right=0, char='a', left=0, map={'a':0}
- right=1, char='b', left=0, map={'a':0, 'b':1}
- right=2, char='b', 发现重复.map['b']是1.left 更新为 Math.Max(0, 1 + 1) = 2.此时 left=2, map={'a':0, 'b':2}.窗口是"b".
- right=3, char='a', 发现重复.map['a']是0.
  - 如果用 left = map['a'] + 1,left 会变成 0 + 1 = 1.但我们当前的 left 已经是 2 了！指针向左回退了,这是错误的,因为窗口的起始点不应该回到一个已经被判定为无效的位置.
  - 如果用 left = Math.Max(left, map['a'] + 1),left 会变成 Math.Max(2, 0 + 1) = 2.left 保持在 2,逻辑正确.这说明重复的 'a' (在索引0) 早已在当前窗口 [2, 3] 的左边,对我们没有影响,无需移动左边界.

可能的实际应用

滑动窗口:
- 性能监控: 我们可以写一个简单的性能分析工具,它记录最近60帧的Time.deltaTime.用滑动窗口可以实时计算出过去1秒（60帧）内的平均帧率、最低帧率等,如果低于某个阈值就发出警告.
- AI行为分析: 分析NPC或敌人在过去一段时间内的行为序列,判断其是否在重复某个模式,从而做出反制.
Dictionary (哈希表):
- 对象池管理: 使用 Dictionary<string, Queue<GameObject>> 来管理不同种类的预制体对象池,通过预制体名称（string）快速找到对应的对象队列.
- 资源缓存: 加载过的AudioClip, Texture2D等资源可以存入 Dictionary<string, Object>,键是资源路径,值是资源本身.再次使用时先从字典中查找,避免重复的磁盘IO.这在Unity中是优化加载性能的常用手段.
- 状态机 (FSM): 用 Dictionary<MyStateEnum, IState> 来存储状态枚举和对应的状态逻辑类,可以非常方便地切换和管理对象（玩家、敌人、UI）的状态.

第四题: 寻找两个正序数组的中位数(难度: 困难)

原题:

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

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

示例 1:

1
2
3

输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2

示例 2:

1
2
3

输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5

提示:

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

开始解题

这道题目要求了我们的时间复杂度应该是 O(log(m+n)) , 看到 log 级别的复杂度,我们的第一反应通常是二分搜索

但是我们应该在哪里进行二分搜索了

一个比较直观但是不符合要求的思路是:

创建一个新的大数组.
将 nums1 和 nums2 合并到这个大数组中并排序.
根据大数组的长度是奇数还是偶数,直接找到中位数.
这个方法的时间复杂度是 O(m+n)（合并过程）,空间复杂度也是 O(m+n),不满足题目 O(log(m+n)) 的时间复杂度要求.因此,我们必须寻找更巧妙的办法.

核心思想: 寻找"分割线"而不是"中位数"

这道题的精髓在于,我们不直接去寻找具体的中位数数值,而是去寻找一个"分割线",这个分割线能把两个数组划分成"左半部分"和"右半部分",并且同时满足以下两个条件:

长度相等: 左半部分所有的元素个数 = 右半部分所有元素的个数(或当总数为奇数时,左半部分比右半部分多一个)
顺序正确: 左半部分的所有元素 <= 右半部分的所有元素

那么当我们找到了这个分割线之后1,中位数就由分割线两侧的元素决定了

那么我们应该如何寻找这个"分割线"呢

我们用二分搜索来寻找这条分割线在其中一个数组(比如 num1 )中的位置

定义分割线:
假设我们在 nums1 的索引 i 处切一刀,把 nums1 分成 nums1[0...i-1] (左半部分) 和 nums1[i...m-1] (右半部分).
为了满足上面提到的“长度相等”条件,nums2 的分割线位置 j 就被确定了.如果两个数组总长度为 total = m + n,我们希望左半部分总共有 (total + 1) / 2 个元素.这个公式很巧妙,无论 total 是奇数还是偶数都适用.
所以,i + j = (m + n + 1) / 2,从而 j = (m + n + 1) / 2 - i.
二分搜索过程:
我们在较短的那个数组（假设是 nums1）上进行二分搜索,搜索范围是 [0, m],目的是找到一个合适的 i.
- 在每一次循环中,我们取一个中间位置 i.
- 根据 i 计算出 j.
- 现在我们有了四个关键的“边界值”:
  - nums1 左半部分的最大值: maxLeft1 = nums1[i-1]
  - nums1 右半部分的最小值: minRight1 = nums1[i]
  - nums2 左半部分的最大值: maxLeft2 = nums2[j-1]
  - nums2 右半部分的最小值: minRight2 = nums2[j]
判断分割是否正确:
要满足“顺序正确”的条件,必须保证 左半部分的最大值 ≤ 右半部分的最小值.具体来说,就是:
maxLeft1 ≤ minRight2 并且 maxLeft2 ≤ minRight1
调整二分搜索范围:
- 如果 maxLeft1 > minRight2:说明 nums1 的分割点 i 太靠右了,导致 nums1 左边的元素太大.我们需要把 i 向左移动.在二分搜索中,这意味着收缩右边界 high = i - 1.
- 如果 maxLeft2 > minRight1:说明 nums1 的分割点 i 太靠左了,导致 nums2 左边的元素太大（因为 i 小了,j 就会变大）.我们需要把 i 向右移动.在二分搜索中,这意味着收缩左边界 low = i + 1.
- 如果上述两个条件都满足,那我们就找到了完美的分割线 i 和 j.

那当我们找到分割线之后,要如何计算中位数呢

如果总长度 (m+n) 是奇数:中位数就是左半部分所有元素里的那个最大值.即 max(maxLeft1, maxLeft2).
如果总长度 (m+n) 是偶数:中位数是左半部分最大值和右半部分最小值的平均数.即 (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0.

举个栗子:`nums1 = [1,3]`, `nums2 = [2]`

m=2, n=1, total=3.左半部分应有 (3+1)/2 = 2 个元素.
我们在 nums1 上二分搜索 i.搜索范围 [0, 2].
尝试1: low=0, high=2 -> i = 1.
- j = (3+1)/2 - i = 2 - 1 = 1.
- 分割如下:
  - nums1 左: [1] (maxLeft1=1) | nums1 右: [3] (minRight1=3)
  - nums2 左: [2] (maxLeft2=2) | nums2 右: [] (空)
- 检查条件:maxLeft2 (2) > minRight1 (3) ？不成立.
- 检查条件:maxLeft1 (1) > minRight2 ？minRight2 不存在,我们先不考虑这个边界.
- 我们发现 maxLeft2 > maxLeft1,但 maxLeft2 并没有大于 minRight1.
- 让我们重新检查条件:maxLeft1(1) <= minRight2(不存在) 和 maxLeft2(2) <= minRight1(3).
- 2 <= 3 是成立的.另一个条件因为 minRight2 不存在,我们可以认为它也成立（在代码实现中会用 int.MaxValue 处理）.
- 所以,分割是正确的！
计算中位数:
- 总长度是3（奇数）.
- 中位数是左半部分的最大值:max(maxLeft1, maxLeft2) = max(1, 2) = 2.
- 最终结果是 2.0.

更形象的理解方式:切卡片游戏

想象一下,nums1 和 nums2 是两摞已经按数字从小到大排好序的卡片.

我们的目标:找到一个“想象中的”合并后的大卡片堆的中位数.

中位数的本质是什么？ 它就是一条分割线,这条线恰好把所有卡片分成数量相等的“左半堆”和“右半堆”,并且左半堆里最大的那张卡片,一定小于等于右半堆里最小的那张卡片.

直接合并的笨办法:把两摞卡片拿过来,一张一张比较,排成新的一大摞,然后从中间拿起那张卡片.这就是 O(m+n) 的方法,太慢了.

聪明的办法（二分搜索）:我们不真的去合并,我们只在这两摞卡片上“比划”一下,找到那条完美的“分割线”应该切在哪里.

游戏开始:

确定目标:假设 nums1 有 m 张,nums2 有 n 张.总共 m+n 张. 我们的“左半堆”需要有 k = (m+n+1)/2 张卡片.（这个 +1 的技巧可以同时兼容总数是奇数和偶数的情况,非常方便）.
核心问题:我们怎么凑够这 k 张卡片作为“左半堆”呢？我们可以从 nums1 里拿 i 张,那么就必须从 nums2 里拿 j = k - i 张. 看到了吗？只要我们确定了在 nums1 上切一刀的位置（i）,在 nums2 上的切分位置（j）就自动确定了！
二分搜索的用武之地:我们的任务就是找到那个刚刚好的 i. i 的取值范围是从 0 (一张都不从nums1拿) 到 m (把nums1全拿了). 我们不用一个一个地去试 i=0, i=1, i=2...,那样太慢了.我们可以用“猜”的办法,也就是二分搜索.

猜 `i` 的过程:

假设 nums1 = [1, 2], nums2 = [3, 4] m=2, n=2, 总数是4.左半堆需要 k = (4+1)/2 = 2 张卡片. 我们在 nums1 上猜一个切割位置 i（i 的范围是 [0, 2]）.

第一次猜:我们猜中间,i = 1.
- 这意味着我们从 nums1 拿 1 张卡片 [1] 作为左半堆的一部分.
- 为了凑够2张,我们必须从 nums2 拿 j = 2 - 1 = 1 张卡片 [3].
- 现在我们想象中的“左半堆”是 {1, 3},“右半堆”是 {2, 4}.
- 检查一下这个分割是否合格？
  - 左半堆最大的卡片是 3.
  - 右半堆最小的卡片是 2.
  - 出问题了！3 > 2！这不符合“左边都比右边小”的规则.
- 分析原因:左半堆的 3 (来自nums2) 太大了.说明我们从 nums2 拿得太多了,j 太大了.因为 j = k - i,所以是我们的 i 猜得太小了.
- 调整策略:既然 i=1 太小,那正确答案肯定在 i 的右边.我们接下来在 [2, 2] 的范围里猜.
第二次猜:范围 [2, 2] 里只能猜 i = 2.
- 这意味着我们从 nums1 拿 2 张卡片 [1, 2].
- 为了凑够2张,我们必须从 nums2 拿 j = 2 - 2 = 0 张卡片 [].
- 现在我们想象中的“左半堆”是 {1, 2},“右半堆”是 {3, 4}.
- 再次检查:
  - 左半堆最大的卡片是 2.
  - 右半堆最小的卡片是 3.
  - 2 <= 3,完美！
- 找到答案了！ 这就是我们要的分割.

总结一下: 二分搜索不是在数组的值 [1,2,3,4] 上搜索,而是在分割点的位置 i ([0, m]) 上进行搜索. 每一次猜测一个 i,我们就得到了一个“候选分割方案”.然后我们通过检查 nums1[i-1]、nums1[i]、nums2[j-1]、nums2[j] 这四个边界值,来判断我们的 i 是猜大了、猜小了,还是刚刚好.从而不断缩小 i 的搜索范围,直到找到最终答案.

解法代码:

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        // 1. 预处理:确保nums1是较短的数组
        // 这样做可以优化二分查找的范围,使其在更小的集合上进行,提高效率.
        if (nums1.Length > nums2.Length) {
            return FindMedianSortedArrays(nums2, nums1);
        }

        // 2. 初始化变量
        int m = nums1.Length;
        int n = nums2.Length;
        // low 和 high 是二分查找在短数组nums1上的搜索范围
        int low = 0;
        int high = m;
        // halfLen 是合并后数组左半部分的元素总数
        int halfLen = (m + n + 1) / 2;

        // 3. 二分查找过程
        while (low <= high) {
            // i 是 nums1 分割线右侧第一个元素的索引,也是其左侧部分的元素个数
            int i = low + (high - low) / 2;
            // j 是 nums2 分割线右侧第一个元素的索引,由 i 推导得出
            int j = halfLen - i;

            // 4. 移动分割线 i
            if (i < high && nums2[j - 1] > nums1[i]) {
                // i 太小了,需要向右移动,增大 i
                // nums2左侧最大值 > nums1右侧最小值,说明i的分割点需要右移
                low = i + 1;
            } else if (i > low && nums1[i - 1] > nums2[j]) {
                // i 太大了,需要向左移动,减小 i
                // nums1左侧最大值 > nums2右侧最小值,说明i的分割点需要左移
                high = i - 1;
            } else {
                // 5. 找到了完美的分割线 i,计算中位数
                
                // 确定左半部分的最大值
                int maxLeft;
                if (i == 0) { // nums1的左侧部分为空
                    maxLeft = nums2[j - 1];
                } else if (j == 0) { // nums2的左侧部分为空
                    maxLeft = nums1[i - 1];
                } else {
                    maxLeft = Math.Max(nums1[i - 1], nums2[j - 1]);
                }

                // 如果总元素个数是奇数,中位数就是左半部分的最大值
                if ((m + n) % 2 == 1) {
                    return maxLeft;
                }

                // 如果总元素个数是偶数,还需要确定右半部分的最小值
                int minRight;
                if (i == m) { // nums1的右侧部分为空
                    minRight = nums2[j];
                } else if (j == n) { // nums2的右侧部分为空
                    minRight = nums1[i];
                } else {
                    minRight = Math.Min(nums1[i], nums2[j]);
                }

                // 中位数是左半部分最大值和右半部分最小值的平均数
                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0;
    }
}

这里特别难理解,我再讲一下吧(从4.移动分割线 i 开始)

场景回顾:

我们已经进入了 while 循环.在循环的每一次迭代中,我们都做了一件事:在 nums1 上“试探性地”切了一刀,位置是 i.然后根据 i 计算出了 nums2 上配套的切割位置 j.

现在,我们手上有四个关键的“边界”数字:

nums1[i-1]:nums1 左半部分的最大值 (L1_Max)
nums1[i]:nums1 右半部分的最小值 (R1_Min)
nums2[j-1]:nums2 左半部分的最大值 (L2_Max)
nums2[j]:nums2 右半部分的最小值 (R2_Min)

我们的终极目标:找到一个 i,使得 L1_Max <= R2_Min 并且 L2_Max <= R1_Min. 这意味着我们找到了完美的分割,左边的都比右边的小.

现在,我们来逐行分析代码是如何实现这个目标的.

深入讲解 `if-else if-else` 逻辑

1. `if (i < high && nums2[j - 1] > nums1[i])`

代码翻译:这个条件检查的是 L2_Max > R1_Min.也就是 nums2 左边的最大值,是否大于 nums1 右边的最小值.
意味着什么？ 如果这个条件成立,说明我们的分割出错了.我们把一个本应属于“右半堆”的小数字(nums1[i])留在了右边,却把一个本应属于“左半堆”的大数字(nums2[j-1])划入了左边.
用栗子说话: nums1 = [10, 20], nums2 = [1, 2, 3]
- m=2, n=3, halfLen = (2+3+1)/2 = 3.
- 假设我们二分查找到 i=1.那么 j = 3 - 1 = 2.
- 分割如下:
  - nums1 左: [10] (L1_Max=10) | nums1 右: [20] (R1_Min=20)
  - nums2 左: [1, 2] (L2_Max=2) | nums2 右: [3] (R2_Min=3)
- 此时 L2_Max(2) <= R1_Min(20),但 L1_Max(10) > R2_Min(3).我们的代码会进入下一个 else if 分支.
再看一个例子: nums1 = [1, 5], nums2 = [2, 3, 4, 6]
- m=2, n=4, halfLen = (2+4+1)/2 = 3.
- 假设我们二分查找到 i=1.那么 j = 3 - 1 = 2.
- 分割如下:
  - nums1 左: [1] (L1_Max=1) | nums1 右: [5] (R1_Min=5)
  - nums2 左: [2, 3] (L2_Max=3) | nums2 右: [4, 6] (R2_Min=4)
- 此时 L1_Max(1) <= R2_Min(4) 成立.但 L2_Max(3) <= R1_Min(5) 也成立.这是完美分割！
回到这个 if 判断:nums2[j - 1] > nums1[i]
- 原因分析:这个不等式成立,说明 i 的值太小了.因为 i 小,导致 j = halfLen - i 的值偏大,使得我们从 nums2 中取了太多的元素进入左半部分,其中就包括了那个“太大”的 nums2[j-1].
- 如何修正:我们需要增大 i.在二分搜索中,这意味着正确答案在当前 i 的右侧.所以我们更新搜索区间的下界:low = i + 1.

2. `else if (i > low && nums1[i - 1] > nums2[j])`

代码翻译:这个条件检查的是 L1_Max > R2_Min.也就是 nums1 左边的最大值,是否大于 nums2 右边的最小值.
意味着什么？ 这同样说明分割出错了.我们把一个“太大”的数字 nums1[i-1] 划入了左半堆.
原因分析:这个不等式成立,说明 i 的值太大了.因为 i 大,我们从 nums1 中取了太多的元素进入左半部分,其中就包括了那个“太大”的 nums1[i-1].
如何修正:我们需要减小 i.在二分搜索中,这意味着正确答案在当前 i 的左侧.所以我们更新搜索区间的上界:high = i - 1.

3. `else`

代码翻译:如果上面两个 if 都不成立,这意味着什么？
- nums2[j - 1] <= nums1[i] 并且
- nums1[i - 1] <= nums2[j]
意味着什么？ 这就是我们寻找到的完美分割,我们成功地把两个数组划分成了左右两半,并且左半部分的所有元素都小于等于右半部分的所有元素.
接下来做什么？ 计算中位数！

深入讲解中位数计算 (在 `else` 块内)

现在我们已经找到了完美的 i 和 j.

1. 计算 `maxLeft` (左半部分的最大值)

左半部分由 nums1 的前 i 个元素和 nums2 的前 j 个元素组成.它的最大值,必然是 nums1[i-1] 和 nums2[j-1] 中较大的那一个.

但是,这里有边界情况需要处理:

if (i == 0): nums1 的左半部分是空的,那么整个左半部分的最大值就是 nums2[j-1].
else if (j == 0): nums2 的左半部分是空的,那么整个左半部分的最大值就是 nums1[i-1].
else: 两边都不为空,maxLeft 就是 Math.Max(nums1[i-1], nums2[j-1]).

2. 判断总长度是奇数还是偶数

if ((m + n) % 2 == 1): 如果总长度是奇数,中位数就是正中间那个数.在我们的分割方案里,左半部分比右半部分多一个元素,这个多出来的元素 maxLeft 就是中位数.所以直接 return maxLeft.

3. 计算 `minRight` (右半部分的最小值) - 仅在总长度为偶数时需要

如果总长度是偶数,中位数是中间两个数的平均值.我们已经找到了左边最大的 maxLeft,现在需要找右边最小的 minRight.

右半部分由 nums1 从 i 开始的元素和 nums2 从 j 开始的元素组成.它的最小值,必然是 nums1[i] 和 nums2[j] 中较小的那一个.

同样,处理边界情况:

if (i == m): nums1 的右半部分是空的！那么整个右半部分的最小值就是 nums2[j].
else if (j == n): nums2 的右半部分是空的！那么整个右半部分的最小值就是 nums1[i].
else: 两边都不为空,minRight 就是 Math.Min(nums1[i], nums2[j]).

4. 返回最终结果 (总长度为偶数)

中位数是 (maxLeft + minRight) / 2.0.使用 2.0 来确保结果是 double 类型的浮点数,而不是整数除法.

知识点总结：

二分搜索的泛化应用：二分搜索的核心是“在一个有序的集合中，通过不断排除一半的可能性来寻找目标”。这个“集合”不一定是一个存有具体数值的数组。它可以是答案的可能范围、索引的范围，或者任何具有单调性的抽象概念。在这道题中，我们搜索的就不是一个值，而是一个满足特定条件的“分割点索引”。
问题转化的思想：直接解决一个问题可能很困难，但我们可以尝试将其转化为一个等价且更容易解决的问题。这道题的精髓就是将“寻找中位数”这个目标，转化为了“寻找一个完美的分割线”。一旦找到了这条线，中位数就自然浮现了。
边界条件的严谨处理：算法的正确性很大程度上取决于对边界条件的正确处理。在这道题中，分割点 i 或 j 可能会取到 0 或者数组的长度 m/n，这意味着某一个“左半部分”或“右半部分”可能是空的。代码中通过 if (i == 0) 等判断来处理这些边界，是保证算法健壮性的关键。
利用不变量和约束：在我们的算法中，i + j = halfLen 是一个恒成立的约束条件（不变量）。这个约束极大地简化了问题，让我们只需要在一个变量 i 上进行搜索，另一个变量 j 就会被自动确定。在设计算法时，寻找并利用这样的不变量，可以有效降低问题的复杂度。

练习题：

选择题

问题： 在解决 “寻找两个正序数组的中位数” 这个问题时，我们使用二分搜索的主要目的是什么？

(A) 在合并后的大数组中快速查找中位数的值。

(B) 在两个数组中分别查找值为中位数的元素。

(D) 减少将两个数组合并所需的时间复杂度。

简答题

问题： 在该算法中，我们将“寻找中位数”问题转化为了“寻找完美分割线”的问题。请简述我们是如何判断一个分割线（由 nums1 的分割点 i 和 nums2 的分割点 j 定义）是否是“完美”的？

参考答案

选择题答案是 ©。

解析：

(A) 是错误的，该算法的核心就是避免了合并数组。
(B) 是错误的，中位数的值可能并不存在于任何一个原始数组中（例如 [1,2] 和 [3,4] 的中位数是2.5）。
(D) 虽然结果上确实避免了 O(m+n) 的合并，但二分搜索的直接目的不是“减少合并时间”，而是作为一种“不合并”的解决方案，其搜索目标是分割点，而非优化合并本身。

简答题参考答案：

一个分割线是“完美”的，需要同时满足两个交叉条件：

nums1 左半部分的最大值 (nums1[i-1]) 必须小于或等于 nums2 右半部分的最小值 (nums2[j])。
nums2 左半部分的最大值 (nums2[j-1]) 必须小于或等于 nums1 右半部分的最小值 (nums1[i])。

这两个条件确保了所有划分到“左半堆”的元素都小于或等于所有划分到“右半堆”的元素，这正是中位数分割线的本质定义。

可能的实际应用

游戏开发 (性能优化)：假设我们要在一个巨大的有序列表（如排行榜、伤害记录）中找到第 K 名的玩家或数据，而这个列表分布在多个服务器或文件中。使用类似的思想，我们可以在不合并所有数据的情况下，高效地定位到第 K 个元素。
资源调度与负载均衡：想象一下，我们有两组服务器，每组的服务器按负载从低到高排序。我们想重新分配任务，使得所有服务器的中位数负载最低。这个问题就可以借鉴本题的思路，通过二分查找寻找一个最优的分配方案，而不是暴力尝试所有可能性。
数据分析与统计：在处理海量数据流时，数据可能被分片存储在不同的地方。当需要计算全局的百分位数（中位数是50%分位数）时，这种分治和二分的思想可以让我们在不加载全部数据到内存的情况下，高效地估算出结果。

力扣刷题日常(3-4)

第三题: 无重复字符的最长子串(难度: 中等)

原题:

开始解题:

方法一: 暴力求解

方法二: 滑动窗口

比喻解释:

解法代码:

知识点解析:

额外练习题:

选择题

简答题

参考答案

可能的实际应用

第四题: 寻找两个正序数组的中位数(难度: 困难)

原题:

开始解题

核心思想: 寻找"分割线"而不是"中位数"

那么我们应该如何寻找这个"分割线"呢

那当我们找到分割线之后,要如何计算中位数呢

举个栗子:nums1 = [1,3], nums2 = [2]

更形象的理解方式:切卡片游戏

游戏开始:

猜 i 的过程:

解法代码:

这里特别难理解,我再讲一下吧(从4.移动分割线 i 开始)

场景回顾:

深入讲解 if-else if-else 逻辑

1. if (i < high && nums2[j - 1] > nums1[i])

2. else if (i > low && nums1[i - 1] > nums2[j])

3. else

深入讲解中位数计算 (在 else 块内)

1. 计算 maxLeft (左半部分的最大值)

2. 判断总长度是奇数还是偶数

3. 计算 minRight (右半部分的最小值) - 仅在总长度为偶数时需要

4. 返回最终结果 (总长度为偶数)

知识点总结：

练习题：

选择题

简答题

参考答案

可能的实际应用

举个栗子:`nums1 = [1,3]`, `nums2 = [2]`

猜 `i` 的过程:

深入讲解 `if-else if-else` 逻辑

1. `if (i < high && nums2[j - 1] > nums1[i])`

2. `else if (i > low && nums1[i - 1] > nums2[j])`

3. `else`

深入讲解中位数计算 (在 `else` 块内)

1. 计算 `maxLeft` (左半部分的最大值)

3. 计算 `minRight` (右半部分的最小值) - 仅在总长度为偶数时需要