1
0
0
LeetCode3-无重复字符的最长子串
文章摘要
|
滑动窗口
说实话，我第一次做这个题的时候感觉不太好做，滑动窗口理解起来不难，但是套在哈希去实践应用，一上来还真有点难理解逻辑。不过思路大体是相同的。这次就详细说下吧。
首先我们把这个字符串S放到数组chars里。
然后我们定义窗口左边界，left = 0，然后我们定义一个ans用来记录最大字串数。
定义右边界right（这里有点双指针那味了，right为本次快指针），如果right没有走到窗口末尾则证明还有可能出现更长字串，所以进行循环。
我们把每一个chars中的字母作为key记录在哈希map charNum里面，value则对应他出现的次数。
如果一个字母出现次数大于1了，则代表该不重复子串的长度已经到了最大值了，如abcwsa，出现第二个a的时候则最大长度为abcws=5。所以此时对于从左边界第一个字母开始的子串已达最大。接下来我们就移动左边界，则 left++ ，重复判断直到该字母出现次数不大于1才终止循环，同时由于字母顺序是不变的，所以对于剩下已经遍历完的子串来说一定不是重复的，则我们仅需要继续移动右边界重复这个过程。
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character,Integer> charNum = new HashMap<>();
char[] chars = s.toCharArray();
int left = 0;
int ans = 0;
for(int right = 0; right < s.length(); right++){
char c = chars[right];
charNum.put(c, charNum.getOrDefault(c, 0) + 1);
while(charNum.get(c) > 1) {
char leftChar = chars[left];
charNum.put(leftChar, charNum.get(leftChar) - 1);
left++;
}
ans =Math.max(ans, right - left + 1);
}
return ans;
}
}