【笔记】语言实例比较 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，这里为了效率用的 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)$ 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 := 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/