用javascript实现:给一个字符串s, 找出其中不含有重复字符的最长子串的长度 s = ‘abcabcbb’ 3 s = ‘aaaaa’ 1 s = ‘pwwkew’ 3
- User
用javascript实现:给一个字符串s, 找出其中不含有重复字符的最长子串的长度
s = ‘abcabcbb’
3
s = ‘aaaaa’
1
s = ‘pwwkew’
3
- Assistant
/**
- @param {string} s
- @return {number} */ var lengthOfLongestSubstring = function(s) { let maxLength = 0; // 最长无重复子串的长度 let start = 0; // 当前子串起点 let map = new Map(); // 存储字符出现的下标
for (let i = 0; i < s.length; i++) { const char = s[i]; if (map.has(char) && map.get(char) >= start) { // 如果字符已经出现过且在当前子串中 start = map.get(char) + 1; // 子串起点更新为当前字符出现的位置的下一个位置 } map.set(char, i); // 记录字符出现的位置 maxLength = Math.max(maxLength, i - start + 1); // 更新最长无重复子串的长度 }
return maxLength; };
- Assistant
这是一段使用滑动窗口思想的代码,时间复杂度为 O(n),其中 n 是字符串 s 的长度。具体实现如下:
-
初始化 maxLength 和 start 都为 0,map 为空。
-
从左往右遍历字符串 s,对于每一个字符 char:
a. 如果 map 中已经存在该字符且下标大于等于 start,说明这个字符在当前子串中已经出现过,需要将子串的起点 start 更新为该字符出现的下一个位置。
b. 不管 char 是否出现过,都需要更新 map 中 char 对应的下标为当前下标 i。
c. 计算当前子串的长度 i - start + 1 并更新 maxLength。
-
遍历完成后,返回 maxLength。
需要注意的是,map 中存储的是每个字符最后一次出现的下标。因为我们不需要记录重复字符前面的下标,只需要记录最后一次出现的位置就可以计算出最长无重复子串的长度。
-
- Assistant
是的,你的理解是正确的。通过记录最后一次出现的下标,我们可以判断一个字符是否在当前子串中出现过。如果一个字符在当前子串中出现过,那么我们需要将子串的起点更新为该字符出现的下一个位置,才能确保新的子串不包含重复的字符。
以字符串 s = 'abcabcbb' 为例,遍历字符串的过程如下:
-
当 i = 0 时,char = 'a'。将该字符和下标 0 存入 map 中。maxLength 和 start 都为 1。
-
当 i = 1 时,char = 'b'。将该字符和下标 1 存入 map 中。maxLength 和 start 不变,为 1。
-
当 i = 2 时,char = 'c'。将该字符和下标 2 存入 map 中。maxLength 和 start 不变,为 1。
-
当 i = 3 时,char = 'a'。map 中已经存在该字符,且下标等于 0,说明该字符在当前子串中出现过。需要将 start 更新为 1,即子串为 'bca'。maxLength 不变,为 1。
-
当 i = 4 时,char = 'b'。map 中已经存在该字符,且下标等于 1,说明该字符在当前子串中出现过。需要将 start 更新为 2,即子串为 'cab'。maxLength 不变,为 1。
-
当 i = 5 时,char = 'c'。map 中已经存在该字符,且下标等于 2,说明该字符在当前子串中出现过。需要将 start 更新为 3,即子串为 'abc'。maxLength 不变,为 1。
-
当 i = 6 时,char = 'b'。map 中已经存在该字符,且下标等于 4,因为该下标大于等于当前 start,说明该字符在当前子串中出现过。需要将 start 更新为 5,即子串为 'cb'。maxLength 不变,为 1。
-
当 i = 7 时,char = 'b'。map 中已经存在该字符,且下标等于 5,因为该下标大于等于当前 start,说明该字符在当前子串中出现过。需要将 start 更新为 6,即子串为 'b'。maxLength 不变,为 1。
遍历完成后,maxLength 的值为 3,即最长无重复子串为 'abc'。
-
- User
用javascript实现:给一个字符串s, 找出其中不含有重复字符的最长子串的长度
s = ‘abcabcbb’
3
s = ‘aaaaa’
1
s = ‘pwwkew’
3
- Assistant
别担心,这个问题是一个标准的“滑动窗口”问题。我们使用两个指针表示不重复的子串在字符串中的左右边界,并用哈希表存储每个字符最后一次出现的位置。具体实现如下:
/** * @param {string} s * @return {number} */ var lengthOfLongestSubstring = function(s) { let n = s.length; let ans = 0, i = 0, j = 0; let hash = new Map(); while (i < n && j < n) { if (!hash.has(s[j])) { hash.set(s[j], j++); ans = Math.max(ans, j - i); } else { hash.delete(s[i++]); } } return ans; };时间复杂度为 O(n),其中 n 是字符串 s 的长度。空间复杂度取决于哈希表中存储的字符种类,为 O(min(n,m)),其中 m 是字符集的大小。
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.