问题
给定一个字符串s
,找到最长子字符串的长度
没有重复字符。单击here以在Leetcode中打开问题
问题类型:
中等,
示例1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
示例2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
示例3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
方法:
要找到最长的子字符串的长度而无需重复字符,我们可以使用滑动窗口方法。我们将维护两个指示L和R,代表当前子字符串的左侧和右端。我们还将使用标签来跟踪当前子字符串中的字符。
这是该方法的分步说明:
将两个指针l和r初始化为0。初始化一个标签HS以存储当前子字符中的字符,以及Maxi以存储到目前为止找到的最大长度。
从左到右开始通过输入字符串S开始迭代(增量R):
a。如果s.charat(r)不在标签HS中,则意味着我们可以扩展当前基因。因此,将s.charat(r)添加到HS,并更新Maxi是其当前值的最大值和R -L + 1(当前基因的长度)。
b。如果S.Charat(R)已经在HS中,则意味着我们具有重复的字符。我们需要通过从HS中递增L并删除S.Charat(L)来收缩子弦,直到没有重复字符为止。此步骤可确保我们在不重复字符的情况下保持子弦。
继续此过程,直到R到达字符串的末端。
最后,返回Maxi,它表示最长的子字符串的长度而无需重复字符。
Java代码:
这是实现上述方法的Java代码:
class Solution {
public int lengthOfLongestSubstring(String s) {
HashSet<Character> hs = new HashSet<>();
int maxi = 0;
int l = 0;
for (int r = 0; r < s.length(); r++) {
if (!hs.contains(s.charAt(r))) {
hs.add(s.charAt(r));
maxi = Math.max(maxi, r - l + 1);
} else {
while (s.charAt(l) != s.charAt(r)) {
hs.remove(s.charAt(l));
l++;
}
hs.remove(s.charAt(l));
l++;
hs.add(s.charAt(r));
}
}
return maxi;
}
}
时间复杂性:
该解决方案的时间复杂性为O(n),其中n是输入字符串s的长度。这是因为我们一次穿越字符串,对于每个字符,我们执行恒定的时间操作(从哈希集和比较中添加/去除)。因此,整体时间复杂性是线性的。
愉快的编码,
湿婆