无重复字符的最长子串
今天做第三题,无重复字符的最长字串,看着很简单,暴力求解,但是运行效率很差。
题目:
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke"是一个子序列,不是子串。
废话不多说,先上我的菜鸡解题思路(字太丑不要介意):
觉得我的字看不下去的就看下面的文字吧:
(1)定义两个变量maxLength(存放最长字串长度) 和 str(存放临时的字串);
(2)遍历入参字符串;
(3)如果遍历到的字符在str中存在,获取该字符下标,如果子串长度大于maxLength,maxLength就是当前子串长度,而str就是字符下标之后的字符串加上最新的字符;
(4)如果字符不存在str中,str就再拼接上遍历的字符,如果子串长度大于maxLength,maxLength就是当前子串长度。
好了,下面是代码:
class Solution {
public int lengthOfLongestSubstring(String s) {
int maxLength = 0;
String str = "";
for(int i = 0;i < s.length();i ++)
{
char newChar = s.charAt(i);
if(str.contains(Character.toString(newChar)))
{
int index = str.indexOf(newChar);
if(str.length() > maxLength)
{
maxLength = str.length();
}
str = str.substring(index+1)+Character.toString(newChar);
}
else
{
str = str + newChar;
if(str.length() > maxLength)
{
maxLength = str.length();
}
}
}
return maxLength;
}
}
提交了一下,结果很惨。。。。。。。。。。。。。
执行用时 :20 ms, 在所有 Java 提交中击败了24.55%的用户
内存消耗 :40.7 MB, 在所有 Java 提交中击败了5.01%的用户
看了看官方提供的方法,使用的是滑动窗口法。
滑动窗口是数组/字符串问题中常用的抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合,即 [i, j)(左闭,右开)。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如,我们将 [i, j) 向右滑动 1 个元素,则它将变为 [i+1, j+1)(左闭,右开)。
回到我们的问题,我们使用 HashSet 将字符存储在当前窗口 [i, j)(最初 j = i)中。 然后我们向右侧滑动索引 j,如果它不在HashSet 中,我们会继续滑动 j。直到 s[j] 已经存在于 HashSet 中。此时,我们找到的没有重复字符的最长子字符串将会以索引 i开头。如果我们对所有的 i 这样做,就可以得到答案。
代码如下:
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
// try to extend the range [i, j]
if (!set.contains(s.charAt(j))){
set.add(s.charAt(j++));
ans = Math.max(ans, j - i);
}
else {
set.remove(s.charAt(i++));
}
}
return ans;
}
}
执行用时 :9 ms, 在所有 Java 提交中击败了69.81%的用户
内存消耗 :40 MB, 在所有 Java 提交中击败了5.42%的用户
上述的方法最多需要执行 2n 个步骤。事实上,它可以被进一步优化为仅需要 n 个步骤。我们可以定义字符到索引的映射,而不是使用集合来判断一个字符是否存在。 当我们找到重复的字符时,我们可以立即跳过该窗口。
也就是说,如果 s[j]在 [i, j)范围内有与 j'重复的字符,我们不需要逐渐增加 i。 我们可以直接跳过 [i,j']范围内的所有元素,并将 i变为 j' + 1。
优化后的滑动窗口:
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>(); // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return ans;
}
}
执行用时 :7 ms, 在所有 Java 提交中击败了82.96%的用户
内存消耗 :39.7 MB, 在所有 Java 提交中击败了6.86%的用户
加快了2ms,还是挺不错的。
好了,今天的分享就到这里了,欢迎留言评论你的思路和想法。
上一篇: 1126: 布尔矩阵的奇偶性