首页 web前端 js教程 利用滑动窗口技术求最长无重复字符的子串

利用滑动窗口技术求最长无重复字符的子串

Dec 10, 2024 am 11:14 AM

让我们分解解决方案步骤,看看每个步骤是如何工作的

我们假设我们收到以下输入:
Longest Substring Without Repeating Characters with Sliding Window Technique

我们将创建一个空集来存储我们遇到的字母,并创建一个变量来保存我们找到的最长子字符串。
Longest Substring Without Repeating Characters with Sliding Window Technique

现在,我们将检查 right 指向的值是否存在于集合中。如果它不存在,我们会将其添加到集合中并向右移动一步。之后,我们将通过将集合的大小与 longSubstr 变量中存储的值进行比较来更新最长的子字符串。
Longest Substring Without Repeating Characters with Sliding Window Technique

我们将检查 right 指向的值是否在集合中。我们发现它不是,所以我们将它添加到集合中并向右递增 1。之后,我们取集合大小和 longSubstr 中的值之间的最大值。
Longest Substring Without Repeating Characters with Sliding Window Technique

我们检查 right 指向的值是否在集合中,这意味着 c 不在集合中。因此,我们将其添加到集合中,向右递增 1,然后检查最大子字符串。
Longest Substring Without Repeating Characters with Sliding Window Technique

现在,我们检查 right 指向的值(即 a)是否存在于集合中。我们看到它确实如此,因此我们将其从集合中删除并向左前进一步。
Longest Substring Without Repeating Characters with Sliding Window Technique

right指向的值是b,它存在于集合中。

因此,我们将左指针向前移动一步,将 b 从集合中删除。
Longest Substring Without Repeating Characters with Sliding Window Technique

现在我们看到b在集合中,所以我们删除left指向的值并向左前进一步。
Longest Substring Without Repeating Characters with Sliding Window Technique

right指向的值是c,它存在于集合中。
因此,我们将其从集合中删除并向左前进一步。
Longest Substring Without Repeating Characters with Sliding Window Technique

我们将继续使用相同的技术,直到第 17 步,并将得到:
Longest Substring Without Repeating Characters with Sliding Window Technique

这是一个 JavaScript 实现

function longestSubstring(s) {
  let left = 0
  let right = 0

  let maxSubstr = 0
  let set = new Set()

  while (right < s.length) {
    const currentChar = s[right]

    if (!set.has(currentChar)) {
      set.add(currentChar)
      right++
      maxSubstr = Math.max(maxSubstr, right - left) // Update max substring length
    } else {
      set.delete(s[left])
      left++
    }
  }

  return maxSubstr
}

let inputString = 'abcabcbb'
console.log(longestSubstring(inputString)) // Output: 3 ("abc")

登录后复制

以上是利用滑动窗口技术求最长无重复字符的子串的详细内容。更多信息请关注PHP中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

前端热敏纸小票打印遇到乱码问题怎么办? 前端热敏纸小票打印遇到乱码问题怎么办? Apr 04, 2025 pm 02:42 PM

前端热敏纸小票打印的常见问题与解决方案在前端开发中,小票打印是一个常见的需求。然而,很多开发者在实...

神秘的JavaScript:它的作用以及为什么重要 神秘的JavaScript:它的作用以及为什么重要 Apr 09, 2025 am 12:07 AM

JavaScript是现代Web开发的基石,它的主要功能包括事件驱动编程、动态内容生成和异步编程。1)事件驱动编程允许网页根据用户操作动态变化。2)动态内容生成使得页面内容可以根据条件调整。3)异步编程确保用户界面不被阻塞。JavaScript广泛应用于网页交互、单页面应用和服务器端开发,极大地提升了用户体验和跨平台开发的灵活性。

谁得到更多的Python或JavaScript? 谁得到更多的Python或JavaScript? Apr 04, 2025 am 12:09 AM

Python和JavaScript开发者的薪资没有绝对的高低,具体取决于技能和行业需求。1.Python在数据科学和机器学习领域可能薪资更高。2.JavaScript在前端和全栈开发中需求大,薪资也可观。3.影响因素包括经验、地理位置、公司规模和特定技能。

JavaScript难以学习吗? JavaScript难以学习吗? Apr 03, 2025 am 12:20 AM

学习JavaScript不难,但有挑战。1)理解基础概念如变量、数据类型、函数等。2)掌握异步编程,通过事件循环实现。3)使用DOM操作和Promise处理异步请求。4)避免常见错误,使用调试技巧。5)优化性能,遵循最佳实践。

JavaScript的演变:当前的趋势和未来前景 JavaScript的演变:当前的趋势和未来前景 Apr 10, 2025 am 09:33 AM

JavaScript的最新趋势包括TypeScript的崛起、现代框架和库的流行以及WebAssembly的应用。未来前景涵盖更强大的类型系统、服务器端JavaScript的发展、人工智能和机器学习的扩展以及物联网和边缘计算的潜力。

如何使用JavaScript将具有相同ID的数组元素合并到一个对象中? 如何使用JavaScript将具有相同ID的数组元素合并到一个对象中? Apr 04, 2025 pm 05:09 PM

如何在JavaScript中将具有相同ID的数组元素合并到一个对象中?在处理数据时,我们常常会遇到需要将具有相同ID�...

如何实现视差滚动和元素动画效果,像资生堂官网那样?
或者:
怎样才能像资生堂官网一样,实现页面滚动伴随的动画效果? 如何实现视差滚动和元素动画效果,像资生堂官网那样? 或者: 怎样才能像资生堂官网一样,实现页面滚动伴随的动画效果? Apr 04, 2025 pm 05:36 PM

实现视差滚动和元素动画效果的探讨本文将探讨如何实现类似资生堂官网(https://www.shiseido.co.jp/sb/wonderland/)中�...

console.log输出结果差异:两次调用为何不同? console.log输出结果差异:两次调用为何不同? Apr 04, 2025 pm 05:12 PM

深入探讨console.log输出差异的根源本文将分析一段代码中console.log函数输出结果的差异,并解释其背后的原因。�...

See all articles