We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
题目要求连续， 我们考虑使用滑动窗口。 而这道题就是窗口大小不固定的滑动窗口题目，然后让我们求满足条件的窗口大小的最大值，这是一种非常常见的滑动窗口题目。
用一个 hashmap 来建立字符和其出现位置之间的映射。同时维护一个滑动窗口，窗口内的都是没有重复的字符，去尽可能的扩大窗口的大小，窗口不停的向右滑动。
如果当前遍历到的字符从未出现过，那么直接扩大右边界；
如果当前遍历到的字符出现过，则缩小窗口（左边索引向右移动），然后继续观察当前遍历到的字符；
重复（1）（2），直到窗口内无重复元素；
维护一个全局最大窗口 res，每次用出现过的窗口大小来更新结果 res，最后返回 res 获取结果;
最后返回 res 即可;
(图片来自： https://github.com/MisterBooo/LeetCodeAnimation)
使用一个数组来维护滑动窗口，遍历字符串，判断字符是否在滑动窗口数组里
push
max
map
start
end
[start, end]
key
value
ans
/** * @作者：user7746o * @链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/zi-jie-leetcode3wu-zhong-fu-zi-fu-de-zui-chang-zi-/ */ var lengthOfLongestSubstring = function(s) { let arr = [], max = 0 for(let i = 0; i < s.length; i++) { let index = arr.indexOf(s[i]) if(index !== -1) { arr.splice(0, index+1); } arr.push(s.charAt(i)) max = Math.max(arr.length, max) } return max };
/** * @作者：Heternally * @链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/javascriptjie-fa-chao-9998-by-heternally/ */ var lengthOfLongestSubstring = function(s) { let num = 0,res = 0; let m = ''; for (n of s) { if (m.indexOf(n) == -1) { m += n; num++; res = res < num ? num: res; } else { m += n; m = m.slice(m.indexOf(n)+1); num = m.length; } } return res; };
class Solution { public: int lengthOfLongestSubstring(string s) { int ans = 0, start = 0; int n = s.length(); // map<char, int> mp; for(int i=0;i<n;i++) { char alpha = s[i]; if(mp.count(alpha)) { start = max(start, mp[alpha]+1); } ans = max(ans, i-start+1); // 字符位置 mp[alpha] = i; } return ans; } };
/** * @作者：LeetCode-Solution * @链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2/ */ class Solution { public: int lengthOfLongestSubstring(string s) { // 哈希集合，记录每个字符是否出现过 unordered_set<char> occ; int n = s.size(); // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动 int rk = -1, ans = 0; // 枚举左指针的位置，初始值隐性地表示为 -1 for (int i = 0; i < n; ++i) { if (i != 0) { // 左指针向右移动一格，移除一个字符 occ.erase(s[i - 1]); } while (rk + 1 < n && !occ.count(s[rk + 1])) { // 不断地移动右指针 occ.insert(s[rk + 1]); ++rk; } // 第 i 到 rk 个字符是一个极长的无重复字符子串 ans = max(ans, rk - i + 1); } return ans; } };
/** * @作者：pinku-2 * @链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-cshi-xian-/ */ class Solution { public: int lengthOfLongestSubstring(string s) { //s[start,end) 前面包含 后面不包含 int start(0), end(0), length(0), result(0); int sSize = int(s.size()); while (end < sSize) { char tmpChar = s[end]; for (int index = start; index < end; index++) { if (tmpChar == s[index]) { start = index + 1; length = end - start; break; } } end++; length++; result = max(result, length); } return result; } };
class Solution { public int lengthOfLongestSubstring(String s) { int ans = 0, start = 0; int n = s.length(); // Map<Character, Integer> map = new HashMap<>(); for(int i=0;i<n;i++) { char alpha = s.charAt(i); if(map.containsKey(alpha)) { start = Math.max(start, map.get(alpha)+1); } ans = Math.max(ans, i-start+1); // 字符位置 map.put(alpha, i); } return ans; } }
/** * @作者：guanpengchn * @链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-jie-suan-fa-3-wu-zhong-fu-zi-fu-de-zui-chang-z/ */ class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(), ans = 0; Map<Character, Integer> map = new HashMap<>(); for (int end = 0, start = 0; end < n; end++) { char alpha = s.charAt(end); if (map.containsKey(alpha)) { start = Math.max(map.get(alpha), start); } ans = Math.max(ans, end - start + 1); map.put(s.charAt(end), end + 1); } return ans; } }
/** * @作者：VioletKiss * @链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/javati-jie-3wu-zhong-fu-zi-fu-de-zui-chang-zi-chua/ */ class Solution { public int lengthOfLongestSubstring(String s) { int i = 0; int flag = 0; int length = 0; int result = 0; while (i < s.length()) { int pos = s.indexOf(s.charAt(i),flag); if (pos < i) { if (length > result) { result = length; } if (result >= s.length() - pos - 1) { return result; } length = i - pos - 1; flag = pos + 1; } length++; i++; } return length; } }
from collections import defaultdict class Solution: def lengthOfLongestSubstring(self, s: str) -> int: l = 0 ans = 0 counter = defaultdict(lambda: 0) for r in range(len(s)): while counter.get(s[r], 0) != 0: counter[s[l]] = counter.get(s[l], 0) - 1 l += 1 counter[s[r]] += 1 ans = max(ans, r - l + 1) return ans
# @作者：powcai # @链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-dong-chuang-kou-by-powcai/ class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if not s:return 0 left = 0 lookup = set() n = len(s) max_len = 0 cur_len = 0 for i in range(n): cur_len += 1 while s[i] in lookup: lookup.remove(s[left]) left += 1 cur_len -= 1 if cur_len > max_len:max_len = cur_len lookup.add(s[i]) return max_len
# @作者：marcusxu # @链接：链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/python3ti-jie-chao-jian-dan-de-dong-tai-gui-hua-ji/ class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if s == '': return 0 if len(s) == 1: return 1 def find_left(s, i): tmp_str = s[i] j = i - 1 while j >= 0 and s[j] not in tmp_str: tmp_str += s[j] j -= 1 return len(tmp_str) length = 0 for i in range(0, len(s)): length = max(length, find_left(s, i)) return length
The text was updated successfully, but these errors were encountered:
No branches or pull requests
题目描述
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
示例 2:
示例 3:
难度：
相关标签
相关企业
思路
题目要求连续， 我们考虑使用滑动窗口。 而这道题就是窗口大小不固定的滑动窗口题目，然后让我们求满足条件的窗口大小的最大值，这是一种非常常见的滑动窗口题目。
算法：
用一个 hashmap 来建立字符和其出现位置之间的映射。同时维护一个滑动窗口，窗口内的都是没有重复的字符，去尽可能的扩大窗口的大小，窗口不停的向右滑动。
如果当前遍历到的字符从未出现过，那么直接扩大右边界；
如果当前遍历到的字符出现过，则缩小窗口（左边索引向右移动），然后继续观察当前遍历到的字符；
重复（1）（2），直到窗口内无重复元素；
维护一个全局最大窗口 res，每次用出现过的窗口大小来更新结果 res，最后返回 res 获取结果;
最后返回 res 即可;
(图片来自： https://github.com/MisterBooo/LeetCodeAnimation)
维护数组：
使用一个数组来维护滑动窗口，遍历字符串，判断字符是否在滑动窗口数组里
push进数组push进数组max更新为当前最长子串的长度max即可滑动窗口 暴力解法：
map数据结构存储 (k, v)，其中 key 值为字符，value 值为字符位置 +1，加 1 表示从字符位置后一个才开始不重复start，结束位置为endend不断遍历向后，会遇到与[start, end]区间内字符相同的情况，此时将字符作为key值，获取其value值，并更新start，此时[start, end]区间内不存在重复字符start，都会更新其 map 数据结构和结果ans。关键点
复杂度分析
代码
JavaScript 实现
C++ 实现
Java 实现
Python3 实现
其他
The text was updated successfully, but these errors were encountered: