时间戳

首页 > 解决方案 > 我的算法可以被视为 O(n) 吗？“查找具有唯一字符的最长子字符串”

javascript - 我的算法可以被视为 O(n) 吗？“查找具有唯一字符的最长子字符串”

问题描述

我偶然发现了这个练习：

创建一个返回具有唯一字符的最长子字符串的函数。

我只是想知道我提出的解决方案是否已经完成了 O(n) 时间复杂度。

IE：

getMaxSubStr("linkshortener") -> "linkshorte"

只有一个 for 循环没有嵌套，所以这应该是 O(n) 对，让我怀疑的是，当 tempStr 偶然发现一个重复字符时，迭代器会返回到最后一次看到重复字符的字符串索引，这样就增加了需要完成运行时操作并且不确定它是否仍然是 O(n)

async function maxUniqueStr(string) {
  let maxStr = "";
  let tempStr = "";
  let lastSeen = {};

  for (let i = 0; i < string.length; i++) {
    let char = string.charAt(i);

    if (tempStr.includes(char)) {
      i = lastSeen[char];
      tempStr = "";
      console.log("-continue-", i);
      continue;
    }

    tempStr += char;
    maxStr = tempStr.length > maxStr.length ? tempStr : maxStr;
    lastSeen[char] = i;  
  }

  return maxStr;
}

标签： javascriptalgorithmtime-complexitybig-o

解决方案

我喜欢两个指针的方法：

function f(S){
  let maxLength = 1
  let idx = 0
  let l = 0
  let r = 1
  let set = new Set([S[0]])

  for (; l<S.length-1, r<S.length;){
    if (!set.has(S[r]))
      set.add(S[r++])
    else
      set.delete(S[l++])
    let currLength = r - l
    if (currLength > maxLength){
      maxLength = currLength
      idx = l
    }
  }
  return S.substr(idx, maxLength)
}

console.log(f('asaafg'))

推荐阅读