# 3. 无重复字符的最长子串

输入: s = "abcabcbb"

输入: s = "bbbbb"

输入: s = "pwwkew"

请注意，你的答案必须是 子串 的长度，"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 {



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;
}


# 4. 寻找两个正序数组的中位数

输入：nums1 = [1,3], nums2 = [2]

输入：nums1 = [1,2], nums2 = [3,4]

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;
}
}

以下是 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;
}
}


1. 第一个数组中 $m1$ 左侧的元素都小于 $median$。
2. 第二个数组中 $m2=k-m1$ 左侧的元素也都小于 $median$。

1. 第一个数组中下标小于 $m1$ 的元素加上第二个数组中下标小于 $m2$ 的元素刚好可以凑够 $(m+n+1) \div 2$ 个元素。
2. 右侧的元素也满足条件，即第一个数组中下标 $m1$ 和第二个数组中下标 $m2$ 的元素合起来才是中位数。

- n1 和 n2 分别表示数组 nums1 和 nums2 的长度。
- k 表示合并后有序数组的中位数的下标值。
- left 和 right 分别表示二分查找的区间左右端点。
- m1 和 m2 分别表示合并后有序数组的两个部分的分割线在 nums1 中的下标和在 nums2 中的下标。
- c1 和 c2 分别表示两个有序数组在当前分割线下可能的中位数值。

|
7天前
|

13 0
|
7天前
|

[Java·算法·简单] LeetCode 283. 移动零
[Java·算法·简单] LeetCode 283. 移动零
16 2
|
10天前
|

16 3
|
10天前
|

15 2
|
10天前
|

16 1
|
11天前
|

【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题：翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题：翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
26 1
|
4天前
|

【洛谷 P1003】[NOIP2011 提高组] 铺地毯 题解（数组+贪心算法）
**NOIP2011 提高组问题：铺地毯** 在第一象限的颁奖典礼场地，有$n$张地毯按编号顺序铺设。需找出覆盖特定点$(x, y)$的最上方地毯编号。输入包括地毯坐标和点坐标，输出地毯编号或-1表示未覆盖。 样例：给定3张地毯，点$(2,2)$被第3张地毯覆盖，输出3；另一样例点$(4,5)$未被覆盖，输出-1。 $30\%$数据$n\leq2$，$50\%$数据坐标$\leq100$，$100\%$数据$n\leq10^4$，坐标$\leq10^5$。 解决方法：从下到上遍历地毯，更新覆盖点的地毯编号。 AC代码略。
5 0
|
11天前
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
19 0
|
11天前
|

【经典LeetCode算法题目专栏分类】【第11期】递归问题：字母大小写全排列、括号生成
【经典LeetCode算法题目专栏分类】【第11期】递归问题：字母大小写全排列、括号生成
10 0
|
11天前
|

【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集：括号生成、岛屿问题、扫雷游戏
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集：括号生成、岛屿问题、扫雷游戏
12 0