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