Leetcode - 如何使用滑动 window 方法优化我的解决方案以获得 k 长度子字符串中的最大元音数？

Question

我在做leetcode 1456

我想出了一个可行的解决方案，但其中一个 tests 出现“超出时间限制”。我使用了滑动 window 方法，我相信我的解决方案是 O(n)（或者我错了吗？）。

var maxVowels = function(s, k) {
   let left = 0;
   let right = 0;
   let maxVowels = 0;
   let curVowels = 0;
   let vowels = ['a','e','i','o','u'];

   while (right < s.length) {
       let subStringLength = right - left + 1;
       if (vowels.includes(s[right])) curVowels++;
       
       if (subStringLength === k) {
           maxVowels = Math.max(maxVowels, curVowels);
           if (maxVowels === k) return maxVowels;
           curVowels = 0;
           left++;
           right = left - 1;
       }           
       right++;
   }
   return maxVowels;
};

我试着看看是不是因为 vowels.includes(s[right]) 方法在某种程度上是一种非常慢的方法，但根据我读到的内容，情况并非如此，特别是因为我的数组只有 5 个长度。

如何优化我的解决方案以使其通过测试？

Answer 1

在@Bergi 的帮助下最终修复了我的代码。

我原来的答案的问题是我一直通过 right = left - 1 重置右指针，而不是仅仅通过增加右指针来“滑动 window”。我最初的解决方案无法大规模使用。它是 O(n*k) 而不是我最初认为的 O(n)。

而且因为我一直将右指针重置为 right = left - 1，所以我实际上对同一个字符做了很多 re-checking。

我的新解决方案（已通过）现在看起来像这样：

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
 var maxVowels = function(s, k) {
    let left = 0;
    let right = 0;
    let maxVowels = 0;
    let curVowels = 0;
    let vowels = ['a','e','i','o','u'];
    
    while (right < s.length) {
        let subStringLength = right - left + 1;
        if (vowels.includes(s[right])) curVowels++;
        
        if (subStringLength === k) {
            maxVowels = Math.max(maxVowels, curVowels);
            if (vowels.includes(s[left])) curVowels--;
            left++;
        }
        
        right++;
        if (maxVowels === k) return maxVowels;
    }
    return maxVowels;
};

Leetcode - 如何使用滑动 window 方法优化我的解决方案以获得 k 长度子字符串中的最大元音数？

Leetcode - how to optimize my solution using sliding window approach for maximum number of vowels in a substring of k length?

javascript

algorithm

sliding-window