目录
题目一：3. 无重复字符的最长子串 - 力扣（LeetCode）
题目描述
为什么选择“滑动窗口 + 哈希表”？
解题思路：滑动窗口 + 哈希表
Java 代码实现
题目二：4. 寻找两个正序数组的中位数 - 力扣（LeetCode）
题目描述
为什么选择“双指针合并法”（以及它的局限）？
Java 代码实现（双指针合并法）
题目一：3. 无重复字符的最长子串 - 力扣（LeetCode）
题目描述
给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入:
s = "abcabcbb"输出:
3解释:因为无重复字符的最长子串是
"abc"，所以其长度为 3。注意"bca"和"cab"也是正确答案。
示例 2:
输入:
s = "bbbbb"输出:
1解释:因为无重复字符的最长子串是
"b"，所以其长度为 1。
示例 3:
输入:
s = "pwwkew"输出:
3解释:因为无重复字符的最长子串是
"wke"，所以其长度为 3。
为什么选择“滑动窗口 + 哈希表”？
看到这道题，我们的思考路径应该是这样的：
抓住关键字：“子串”。子串意味着必须是连续的一段。这与“子序列”（可以不连续）有本质区别。对于连续区间的问题，最常用的思想就是双指针。
抓住关键字：“无重复”。既然要求无重复，我们就需要一个数据结构（通常是哈希表或数组）来记录当前区间内出现了哪些字符及其频次，以便做到 O(1)O(1) 的快速查询。
为什么不用暴力法？如果暴力枚举所有子串，再用哈希表判断是否重复，时间复杂度会达到 O(N2)O(N2) 甚至 O(N3)O(N3)，当字符串很长时一定会超时。
为什么是“滑动窗口”？假设我们已经找到了一个无重复的子串
[left, right]。当我们把右边界right往右移动一个字符时：如果新字符没出现过，那太好了，当前无重复子串变长了，更新答案。
如果新字符出现过，说明当前窗口里有重复元素了。关键来了：我们不需要把
left退回起点重新开始（那是暴力法），因为既然包含了新字符后发生重复，那么只要那个重复的字符还在窗口里，子串就一直不合法。因此，我们只需要把左边界left不断向右移动，直到把那个重复的字符“挤出去”为止。这种
left和right都只向右移动、不回退的特性，被称为单调性，这正是滑动窗口能将时间复杂度降到 O(N)O(N) 的核心原因。
解题思路：滑动窗口 + 哈希表
这道题是经典的滑动窗口（Sliding Window）应用题。
定义两个指针
left和right，分别代表窗口的左右边界。使用一个
HashMap来记录窗口内字符出现的次数。right指针不断向右移动，每次移动将当前字符加入HashMap并计数。当
HashMap中某个字符的计数大于 1 时，说明窗口内出现了重复字符。此时我们需要移动left指针，缩小窗口，直到该字符的计数重新回到 1。在每次循环中，更新当前无重复字符子串的最大长度
ret。
Java 代码实现
class Solution { public int lengthOfLongestSubstring(String s) { char[] str = s.toCharArray(); int n = str.length; int left = 0, right = 0, ret = 0; // 用于记录窗口内字符出现的频次 Map<Character, Integer> hash = new HashMap<>(); while (right < n) { char ch = str[right]; hash.put(ch, hash.getOrDefault(ch, 0) + 1); // 如果当前字符出现次数大于 1，说明窗口内存在重复字符 // 移动左指针，缩小窗口，直到该字符的频次降为 1 while (hash.get(ch) > 1) { hash.put(str[left], hash.get(str[left]) - 1); left++; } // 更新最大长度 ret = Math.max(ret, right - left + 1); right++; } return ret; } }题目二：4. 寻找两个正序数组的中位数 - 力扣（LeetCode）
题目描述
给定两个大小分别为m和n的正序（从小到大）数组nums1和nums2。请你找出并返回这两个正序数组的中位数。
要求：算法的时间复杂度应该为 O(log(m+n))O(log(m+n))。
示例 1:
输入:
nums1 = [1,3], nums2 = [2]输出:
2.00000解释:合并数组 =
[1,2,3]，中位数 2
示例 2:
输入:
nums1 = [1,2], nums2 = [3,4]输出:
2.50000解释:合并数组 =
[1,2,3,4]，中位数 (2 + 3) / 2 = 2.5
为什么选择“双指针合并法”（以及它的局限）？
从这道题的题干中，我们可以提取出几个核心线索：
“两个正序数组”：既然是有序的，那就极大概率可以用到双指针。这就好比我们有两叠按大小排好的扑克牌，要把它们合在一起按顺序排好，最直观的方法就是两只手各拿一叠，每次比较最上面的一张，谁小就先放下。
“中位数”：中位数的定义是将数组排序后处于中间位置的数。这天然就需要我们对数据进行“排序”或者“找第 K 小”的操作。
为什么图片中用了双指针合并？因为这是最符合人类直觉的解法。开辟一个新数组，用两个指针分别遍历两个原数组，每次把较小的元素放入新数组。合并完成后，直接根据新数组的总长度的奇偶性，取出中位数。
这种方法的问题在哪？虽然直观易懂，但它的时间复杂度是O(m+n)O(m+n)，空间复杂度也是O(m+n)O(m+n)。注意题目要求：时间复杂度应为 O(log(m+n))O(log(m+n))。看到
log这个词，我们应该本能地想到“二分查找”。
Java 代码实现（双指针合并法）
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m = nums1.length, n = nums2.length; int[] arr = new int[m + n]; int left = 0, right = 0, i = 0; // 1. 双指针合并两个有序数组 while (left < m || right < n) { // 使用 0x3f3f3f3f 作为无穷大占位符，防止数组越界 int s1 = 0x3f3f3f3f; int s2 = 0x3f3f3f3f; if (left < m) s1 = nums1[left]; if (right < n) s2 = nums2[right]; if (s1 > s2) { arr[i++] = s2; right++; } else { arr[i++] = s1; left++; } } int sum = m + n; if (sum == 0) return 0; // 2. 计算中位数 if (sum % 2 == 0) { // 偶数个元素，中间两个数的平均值 return (double)(arr[sum / 2 - 1] + arr[sum / 2]) / 2; } else { // 奇数个元素，正中间的数 return (double)arr[sum / 2]; } } }
