LeetCode 3. 无重复字符的最长子串

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 3. 无重复字符的最长子串

思路分析

我们可以使用滑动窗口的方法来解决这个问题。具体步骤如下：

定义两个指针：left 和 right，分别表示当前窗口的左右边界。

使用一个哈希集合：用于存储当前窗口中的字符，以便快速判断字符是否重复。

移动右指针：不断扩展窗口，直到遇到重复字符。

移动左指针：当遇到重复字符时，收缩窗口，直到窗口中不再有重复字符。

更新结果：每次更新窗口时，计算当前窗口的长度，并更新最大长度。

参考代码

特例：i = max(i, hashtable.get(c) + 1)

输入: “abba”

输出: 2

解释: 因为无重复字符的最长子串是 “ab / ba”，所以其长度为 2。

func lengthOfLongestSubstring(s string) int {
	charSet := make(map[byte]bool)
	left, maxLength := 0, 0

	for right := 0; right < len(s); right++ {
		// 如果字符重复，收缩窗口
		for charSet[s[right]] {
			delete(charSet, s[left])
			left++
		}
		charSet[s[right]] = true
		maxLength = max(maxLength, right-left+1)
	}

	return maxLength
}

func lengthOfLongestSubstring(s string) int {
	hashmap := make(map[byte]int)
	res := 0
	left, right := 0, 0
	for right < len(s) {
		c := s[right]
		if index, ok := hashmap[c]; ok {
			left = max(left, index+1)
		}
		res = max(res, right-left+1)
		hashmap[c] = right
		right++
	}
	return res
}

func lengthOfLongestSubstring(s string) int {
	left, right, n := 0, 0, len(s)
	visited := make(map[byte]bool)
	res := 0
	for right < n {
		c := s[right]
		for visited[c] {
			delete(visited, s[left])
			left++
		}
		visited[c] = true
		right++
		if right-left > res {
			res = right - left
		}
	}
	return res
}

🍏 点击查看 Java 题解

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int i = 0;
        int res = 0;
        for (int j = 0; j < s.length(); j++) {
            char c = s.charAt(j);
            if (map.containsKey(c)) {
                i = Math.max(i, map.get(c) + 1);
            }
            res = Math.max(res, j - i + 1);
            map.put(c, j);
        }
        return res;
    }
}

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/11034463