语言实例比较 3. 无重复字符的最长子串 C++ Rust Java Python
C++
C++: 9ms O ( N 2 ) O(N^2) O(N2), 8.68MB mem O ( 1 ) O(1) O(1)
滑动窗口循环
class Solution
{
public:
int lengthOfLongestSubstring(const string s) {
//s[start,end) 前面包含 后面不包含
int res(0);
for (int start(0), end(0); end < s.size(); ++end) {
for (int i = start; i < end; ++i)
if (s[end] == s[i]) {
start = i + 1;
break;
}
res = max(res, end - start + 1);
}
return res;
}
};
滑动窗口动态规划哈希表:12ms O ( N ) O(N) O(N), mem 10.88MB O ( N ) O(N) O(N)
窗口左右指针索引
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> last_pos_dic;
int i = 0, res = 0, len = s.size();
for(int j = 0; j < len; j++) {
auto p = last_pos_dic.find(s[j]);
if (p != last_pos_dic.end())
i = max(i, p->second + 1); // 更新左指针
last_pos_dic[s[j]] = j; // 哈希表记录
res = max(res, j - i + 1); // 更新结果
}
return res;
}
};
滑动窗口动态规划哈希表:14ms
仅保存窗口右指针和size
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> hash;
int result = 0;
for (int i = 0, window_size = 0; i < s.size(); ++i) {
int last_pos = hash.find(s[i]) == hash.end() ? -1 : hash.find(s[i])->second; //获取索引
hash[s[i]] = i;
window_size = window_size < i - last_pos ? window_size + 1 : i - last_pos; //发现重复就挪新窗口
result = max(window_size, result);
}
return result;
}
};//https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/2361797/3-wu-zhong-fu-zi-fu-de-zui-chang-zi-chua-26i5/
Rust
impl Solution {
pub fn length_of_longest_substring(s: String) -> i32 {
let chars = s.as_bytes();
let mut ans = 0;
let mut left = 0;
let mut window = vec![false; 128]; // 也可以用 HashSet,这里为了效率用的 Vec
for (right, &c) in chars.iter().enumerate() {
let c = c as usize;
while window[c] { // 加入 c 后,窗口内会有重复元素
window[s[left] as usize] = false;
left += 1;
}
window[c] = true;
ans = ans.max(right - left + 1); // 更新窗口长度最大值
}
ans as i32
}
}
链接:https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/1959540/xia-biao-zong-suan-cuo-qing-kan-zhe-by-e-iaks/
Java
time O ( N ) O(N) O(N) mem O ( N ) O(N) O(N)
class Solution {
public int lengthOfLongestSubstring(String s) {
char[] chars = s.toCharArray(); // 转换成 char[] 加快效率(忽略带来的空间消耗)
int n = chars.length, ans = 0, left = 0;
boolean[] has = new boolean[128]; // 也可以用 HashSet<Character>,这里为了效率用的数组
for (int right = 0; right < n; ++right) {
char c = s[right];
while (has[c]) // 加入 c 后,窗口内会有重复元素
has[s[left++]] = false;
has[c] = true;
ans = Math.max(ans, right - left + 1); // 更新窗口长度最大值
}
return ans;
}
}
链接:https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/1959540/xia-biao-zong-suan-cuo-qing-kan-zhe-by-e-iaks/
Go
time O ( N ) O(N) O(N) mem O ( N ) O(N) O(N)
func lengthOfLongestSubstring(s string) (ans int) {
window := [128]bool{} // 也可以用 map,这里为了效率用的数组
left := 0
for right, c := range s {
for window[c] { // 加入 c 后,窗口内会有重复元素
window[s[left]] = false
left++
}
window[c] = true
ans = max(ans, right-left+1) // 更新窗口长度最大值
}
return
}
func max(a, b int) int { if b > a { return b }; return a }
链接:https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/1959540/xia-biao-zong-suan-cuo-qing-kan-zhe-by-e-iaks/
本文含有隐藏内容,请 开通VIP 后查看