【笔记】语言实例比较 3. 无重复字符的最长子串 C++ Rust Java Python

语言实例比较 3. 无重复字符的最长子串 C++ Rust Java Python

C++

C++: 9ms $O(N^2)$, 8.68MB mem $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)$, mem 10.88MB $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，这里为了效率用的 Vecfor (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)$ mem $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)$ mem $O(N)$

func lengthOfLongestSubstring(s string) (ans int) {window := [128]bool{} // 也可以用 map，这里为了效率用的数组left := 0for right, c := range s {for window[c] { // 加入 c 后，窗口内会有重复元素window[s[left]] = falseleft++}window[c] = trueans = 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/