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` 分别表示两个有序数组在当前分割线下可能的中位数值。