【力扣刷题实战】无重复的最长字串

大家好，我是小卡皮巴拉

文章目录

力扣题目：无重复的最长字串

题目描述

解题思路

问题理解

算法选择

具体思路

解题要点

完整代码（C++）

兄弟们共勉！！！

每篇前言

博客主页：小卡皮巴拉

咱的口号：🌹小比特，大梦想🌹

作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请大佬们批评斧正。

力扣题目：无重复的最长字串

原题链接：3. 无重复字符的最长子串 - 力扣（LeetCode）

题目描述

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

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

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

解题思路

问题理解

题目要求在给定的字符串 s 里找出不包含重复字符的最长子串，然后返回该子串的长度。这里要明确子串是字符串中连续的字符序列，和子序列不同，子序列中的字符可以不连续。

算法选择

使用滑动窗口算法来解决此问题。滑动窗口是一种在处理数组或字符串的子数组、子串问题时常用的算法。它借助两个指针来界定窗口的范围，并且能够动态地调整窗口大小，从而高效地解决问题。

具体思路

定义哈希表：创建一个长度为 128 的数组 hash 来模拟哈希表，数组的下标对应字符的 ASCII 码值，数组元素用于记录该字符在当前窗口中出现的次数。
初始化指针与结果变量：在 lengthOfLongestSubstring 函数中，定义两个指针 left 和 right 分别表示滑动窗口的左右边界，初始时都指向字符串的起始位置。同时，定义变量 ret 用于记录最长无重复子串的长度，初始化为 0。
移动右指针：使用 for 循环让 right 指针从左到右遍历字符串。在每次循环中，将当前字符 s[right] 加入窗口，并更新 hash 数组中该字符的出现次数。
处理重复字符：当 hash[s[right]] > 1 时，说明当前字符在窗口中出现的次数超过 1 次，即窗口内存在重复字符。此时，需要移动 left 指针，将字符从窗口移除，并更新 hash 数组，直到窗口内不再有重复字符。
更新最长长度：每次移动 right 指针后，计算当前窗口的长度 right - left + 1，并将其与 ret 比较，取较大值更新 ret。
返回结果：循环结束后，返回 ret，即最长无重复子串的长度。

解题要点

滑动窗口的维护：要正确处理 left 和 right 指针的移动，确保窗口内始终不包含重复字符。
哈希表的使用：合理利用 hash 数组记录字符的出现次数，通过简单的数组操作就能快速判断是否有重复字符。
结果的更新：每次移动 right 指针后，及时更新最长无重复子串的长度，保证最终结果的正确性。

完整代码（C++）

class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] = { 0 }; // 使用数组来模拟哈希表，数组下标对应字符的 ASCII 码值，数组元素记录该字符在当前窗口中出现的次数int n = s.size(); // 获取字符串的长度int ret = 0; // 用于记录最长无重复子串的长度for(int left = 0, right = 0; right < n; right++) // 定义左右指针，右指针从左到右遍历字符串{hash[s[right]]++; // 将当前字符加入窗口，并更新其在哈希表中的出现次数while(hash[s[right]] > 1) // 判断当前字符在窗口中出现的次数是否超过 1 次，如果超过 1 次，说明窗口内有重复字符hash[s[left++]]--; // 移动左指针，将字符从窗口移除，并更新其在哈希表中的出现次数，直到窗口内不再有重复字符ret = max(ret, right - left + 1); // 计算当前窗口的长度，并更新最长无重复子串的长度}return ret; // 返回最长无重复子串的长度}
};