LeetCode 第 3 题:无重复字符的最长子串 (滑动窗口)

方法:滑动窗口

滑动窗口模板问题:右指针先走,满足了一定条件以后,左指针向前走,直到不满足条件。

特点:左右指针的方向是一致的,并且是不回头的。

C++ 代码:

#include <iostream>
#include <string> using namespace std; class Solution {
public:
int lengthOfLongestSubstring(string s) {
int size = s.size();
if (size < 2) {
return size;
} int left = 0;
int right = 0;
int res = 0;
int count = 0;
int freq[128] = {0};
while (right < size) {
if (freq[s[right]] == 1) {
count++;
}
freq[s[right]]++;
right++;
while (count > 0) {
if (freq[s[left]] == 2) {
count--;
}
freq[s[left]]--;
left++;
}
res = max(res, right - left);
}
return res;
}
};

Java 代码:

/**
* @author liweiwei1419
* @date 2019/9/23 11:34 下午
*/
public class Solution5 { public int lengthOfLongestSubstring(String s) {
int len = s.length();
if (len < 2) {
return len;
}
int res = 0;
// 表示边界条件,重复次数
int count = 0; int[] hash = new int[128];
int left = 0;
int right = 0;
while (right < len) {
if (hash[s.charAt(right)] == 1) {
// 当前看到的 right 多于 1 个,说明此时的滑动窗口有重复元素
count++;
}
hash[s.charAt(right)]++;
right++;
while (count > 0) {
// 如果正好遇到重复的那个字符,就可以退出循环了
if (hash[s.charAt(left)] == 2) {
count--;
}
hash[s.charAt(left)]--;
left++;
}
// 此时 (left, right] 这个区间内没有重复元素
// (3, 5],[4,5]
res = Math.max(res, right - left);
}
return res;
}
}

Python 代码:

class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
size = len(s)
if size < 2:
return size
left = 0
right = 0
hash = [0] * 128
res = 0
count = 0
while right < size:
if hash[ord(s[right])] == 1:
count += 1
hash[ord(s[right])] += 1
right += 1 while count == 1:
if hash[ord(s[left])] == 2:
count -= 1
hash[ord(s[left])] -= 1
left += 1
res = max(res, right - left)
return res
05-11 19:58