3. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
解题代码：
class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(); int[] cnt = new int[128]; int ans = 0, left = 0, right = 0; while (right < n) { cnt[s.charAt(right)]++; while (cnt[s.charAt(right)] > 1) { cnt[s.charAt(left)]--; left++; } ans = Math.max(ans, right - left + 1); right++; } return ans; } }
代码解析：
以上是使用字符数组来代替哈希集合、实现不含重复字符的最长子串长度问题的 Java 代码。这里是每行代码的解释： ``` class Solution { ``` 这是一个类定义，名为 `Solution`。 ``` public int lengthOfLongestSubstring(String s) { ``` 这是一个公共方法 `lengthOfLongestSubstring`，它接受一个字符串类型的参数 `s` 作为输入，表示需要寻找最长不重复子串的字符串。方法返回一个整型的值，表示不含重复字符的最长子串长度。 ``` int n = s.length(); ``` 获取字符串参数的长度 `n`，用于后面的循环遍历。 ``` int[] cnt = new int[128]; ``` 创建一个长度为 128 的整型数组 `cnt`，记录每个字符最后一次在 `s` 中出现的位置。由于所给定字符串只包含 ASCII 字符，因此数组长度为 128。因为 ASCII 的编号范围是 0 ~ 127，共 128 个字符。 ``` int ans = 0, left = 0, right = 0; ``` 初始化最大不重复子串长度为 0，定义左指针 `left` 和右指针 `right` 的初始位置都为字符串的开头位置 0。 ``` while (right < n) { ``` 当 `right` 小于字符串的长度时，我们进行循环。 ``` cnt[s.charAt(right)]++; ``` 将当前位置的字符 `s.charAt(right)` 在数组 `cnt` 中的值增加 1。也就是记录当前对应字符在当前滑动窗口中的出现次数。 ``` while (cnt[s.charAt(right)] > 1) { cnt[s.charAt(left)]--; left++; } ``` 如果当前对应字符的计数器 `cnt[s.charAt(right)]` 的值大于 1，说明当前字符在当前滑动窗口中出现了 2 次或以上，需要将 `left` 指针右移，缩小滑动窗口的大小。同时，需要将当前指向的字符 `s.charAt(left)` 在计数器 `cnt` 中的值减 1。 ``` ans = Math.max(ans, right - left + 1); ``` 更新最长不重复子串的长度 `ans`，值为当前滑动窗口的长度 `right - left + 1` 和 `ans` 的最大值。 ``` right++; ``` 右指针 `right` 向右移动一个位置，扩大滑动窗口的大小。 ``` } return ans; } ``` 返回最终求得的不含重复字符的最长子串的长度 `ans`。
4. 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数 。
算法的时间复杂度应该为 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
解题代码1：
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int n1 = nums1.length, n2 = nums2.length; // 保证 n1 <= n2 if (n1 > n2) { return findMedianSortedArrays(nums2, nums1); } // 分别找到两个数组的分割线左侧的最大值和右侧的最小值 int k = (n1 + n2 + 1) / 2; int left = 0, right = n1; while (left < right) { int m1 = left + right >> 1; int m2 = k - m1; if (nums1[m1] < nums2[m2 - 1]) { left = m1 + 1; } else { right = m1; } } int m1 = left, m2 = k - m1; int c1 = Math.max(m1 <= 0 ? Integer.MIN_VALUE : nums1[m1 - 1], m2 <= 0 ? Integer.MIN_VALUE : nums2[m2 - 1]); if ((n1 + n2) % 2 == 1) { return c1; } int c2 = Math.min(m1 >= n1 ? Integer.MAX_VALUE : nums1[m1], m2 >= n2 ? Integer.MAX_VALUE : nums2[m2]); return (c1 + c2) / 2.0; } }
解题代码2：
以下是 Java 代码实现，时间复杂度为 $O(log (m+n))$： ``` class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int n1 = nums1.length, n2 = nums2.length; // 保证 n1 <= n2 if (n1 > n2) { return findMedianSortedArrays(nums2, nums1); } // 分别找到两个数组的分割线左侧的最大值和右侧的最小值 int k = (n1 + n2 + 1) / 2; int left = 0, right = n1; while (left < right) { int m1 = left + right >> 1; int m2 = k - m1; if (nums1[m1] < nums2[m2 - 1]) { left = m1 + 1; } else { right = m1; } } int m1 = left, m2 = k - m1; int c1 = Math.max(m1 <= 0 ? Integer.MIN_VALUE : nums1[m1 - 1], m2 <= 0 ? Integer.MIN_VALUE : nums2[m2 - 1]); if ((n1 + n2) % 2 == 1) { return c1; } int c2 = Math.min(m1 >= n1 ? Integer.MAX_VALUE : nums1[m1], m2 >= n2 ? Integer.MAX_VALUE : nums2[m2]); return (c1 + c2) / 2.0; } } ``` 具体地，我们将两个数组合并成一个有序数组，并且找到这个有序数组的中位数。为了使算法的时间复杂度为 $O(log (m+n))$，我们需要使用二分查找的思想进行操作。 我们先假设我们已经求出了两个数组合并后的有序数组的中位数，记为 $median$。根据中位数的定义，它将有序数组分成两个部分，左边部分的元素个数为 $(m+n+1) \div 2$。因此，我们只需要在第一个数组中找到一个位置 $m1$，使得： 1. 第一个数组中 $m1$ 左侧的元素都小于 $median$。 2. 第二个数组中 $m2=k-m1$ 左侧的元素也都小于 $median$。 根据第一个数组和第二个数组都是有序的，上述两个条件等价于： 1. 第一个数组中下标小于 $m1$ 的元素加上第二个数组中下标小于 $m2$ 的元素刚好可以凑够 $(m+n+1) \div 2$ 个元素。 2. 右侧的元素也满足条件，即第一个数组中下标 $m1$ 和第二个数组中下标 $m2$ 的元素合起来才是中位数。 因此，我们可以对第一个数组进行二分查找，找到一个位置 $m1$，使得满足上述条件。然后，我们就可以根据 $m1$ 和 $k$ 计算出 $m2$ 的值，进而确定中位数 $median$。 最后，我们计算中位数并返回即可。 上述代码中的变量解释如下： - `n1` 和 `n2` 分别表示数组 `nums1` 和 `nums2` 的长度。 - `k` 表示合并后有序数组的中位数的下标值。 - `left` 和 `right` 分别表示二分查找的区间左右端点。 - `m1` 和 `m2` 分别表示合并后有序数组的两个部分的分割线在 `nums1` 中的下标和在 `nums2` 中的下标。 - `c1` 和 `c2` 分别表示两个有序数组在当前分割线下可能的中位数值。
