算法练习

leetcode

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例：

输入: “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

思路分析

1.暴力法

逐个检查所有的子字符串，看它是否不含有重复的字符。

这个方法思路比较简单，只要列举出所有子字符串，并且找出最长的无重复的子字符串即可。下面给出具体思路：

假设我们有一个函数 boolean allUnique(String substring) ，如果子字符串中的字符都是唯一的，它会返回true，否则会返回false。 我们可以遍历给定字符串 s 的所有可能的子字符串并调用函数 allUnique。 如果事实证明返回值为true，那么我们将会更新无重复字符子串的最大长度的答案。

  1. 为了枚举给定字符串的所有子字符串，我们需要枚举它们开始和结束的索引。假设开始和结束的索引分别为 i 和 j。那么我们有 0 <= i <= j <= n（这里的结束索引 j是按惯例排除的）。因此，使用i从0到n - 1以及j从i+1到n这两个嵌套的循环，我们可以枚举出 s 的所有子字符串。

  2. 要检查一个字符串是否有重复字符，我们可以使用集合。我们遍历字符串中的所有字符，并将它们逐个放入set中。在放置一个字符之前，我们检查该集合是否已经包含它。如果包含，我们会返回 false。循环结束后，我们返回 true。

2.滑动窗口

暴力法非常简单。但它太慢了。那么我们该如何优化它呢？

在暴力法中，我们会反复检查一个子字符串是否含有有重复的字符，但这是没有必要的。如果从索引 i 到 j - 1 之间的子字符串Sij已经被检查为没有重复字符。我们只需要检查s[j]对应的字符是否已经存在于子字符串S ij中。

要检查一个字符是否已经在子字符串中，我们可以检查整个子字符串，这将产生一个复杂度为 O(n^2)的算法，但我们可以做得更好。

通过使用 HashSet 作为滑动窗口，我们可以用 O(1) 的时间来完成对字符是否在当前的子字符串中的检查。

滑动窗口是数组/字符串问题中常用的抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 [i, j)（左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如，我们将 [i, j)向右滑动 1 个元素，则它将变为 [i+1, j+1)（左闭，右开）。

回到我们的问题，我们使用 HashSet 将字符存储在当前窗口 [i, j)（最初 j = i）中。 然后我们向右侧滑动索引 j，如果它不在 HashSet 中，我们会继续滑动 j。直到 s[j] 已经存在于 HashSet 中。此时，我们找到的没有重复字符的最长子字符串将会以索引 i 开头。如果我们对所有的 i 这样做，就可以得到答案。

当然这里还是可以优化的，比如如果 s[j] 在 [i, j) 范围内有与 j’重复的字符，我们不需要逐渐增加 i 。 我们可以直接跳过 [i，j’] 范围内的所有元素，并将 i 变为 j’ + 1。

代码

优化前：

var lengthOfLongestSubString = function(s) {
   const n = s.length;
   let tempStr = "";
   let longestStr = 0;
   let i = 0;
   let j = 0;
   if(!tempStr.includes(s[j])) {
      tempStr += s[j++];
      longestStr = Math.max(longestStr,j-i)
   }else{
      tempStr = s.slice(++i,j)
   }
   return longestStr;
}

优化后：

var lengthOfLongestSubstring = function(s) { 
    const n = s.length;
    let tempStr = "";
    let ans = 0;
    let i = 0;
    let j = 0;
    while (j<n) {
        //表示出现重复元素
        if (tempStr.includes(s[j])) {
            //出现重复元素的下一位
            i = tempStr.lastIndexOf(s[j]) + 1
            //截取重复元素下一位到数组的末尾
            tempStr = tempStr.slice(i) //注意slice是浅拷贝，并不会改变原数组
        }
        ans = Math.max(ans, tempStr.length + 1)
        tempStr += s[j++]
    }

    return ans;
};
赞 赏