★ 算法OJ题 ★ 力扣3 - 无重复字符的最长子串

Ciallo～(∠・ω< )⌒☆ ~ 今天，塞西莉亚将和大家一起做一道滑动窗口算法题-- 无重复字符的最长子串~

目录

一  题目

二  算法解析

三  编写算法

一  题目

3. 无重复字符的最长子串 - 力扣（LeetCode）

二  算法解析

解法⼀：暴力求解 + 哈希表

枚举从每⼀个位置开始往后，无重复字符的子串可以到达什么位置。找出其中长度最大的即可。

在往后寻找无重复子串能到达的位置时，可以利用哈希表统计出字符出现的频次，判断什么时候⼦串出现了重复元素。

时间复杂度：O(N ^ 2)

class Solution {
public:
	int lengthOfLongestSubstring(string s) {
		int ret = 0; // 记录结果
		int n = s.length();
		// 1. 枚举从不同位置开始的最⻓重复⼦串
		// 枚举起始位置
		for (int i = 0; i < n; i++)
		{
			// 创建⼀个哈希表，统计频次
			int hash[128] = { 0 };

			// 寻找结束为⽌
			for (int j = i; j < n; j++)
			{
				hash[s[j]]++; // 统计字符出现的频次
				if (hash[s[j]] > 1) // 如果出现重复的
					break;

				// 如果没有重复，就更新 ret
				ret = max(ret, j - i + 1);
			}
		}
		// 2. 返回结果
		return ret;
	}
};

解法二：滑动窗口

解法一可以通过以下优化，缩短时间复杂度：~

算法思路：

让滑动窗口满⾜：窗口内所有元素都是不重复的。

右端元素 ch 进⼊窗⼝的时候，哈希表统计这个字符的频次：

• 如果这个字符出现的频次超过 1 ，说明窗⼝内有重复元素，那么就从左侧开始划出窗⼝， 直到 ch 这个元素的频次变为 1 ，然后再更新结果。
• 如果没有超过 1 ，说明当前窗⼝没有重复元素，可以直接更新结果

时间复杂度：O(N)

三  编写算法

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[128] = { 0 }; // 使⽤数组来模拟哈希表
        int left = 0, right = 0, ret = 0;
        int n = s.size();
        while(right < n)
        {
            hash[s[right]]++; // 进⼊窗⼝
            while(hash[s[right]] > 1) // 判断
            {
                // 出窗⼝
                hash[s[left]]--;
                left++;
            }
            ret = max(ret, right - left + 1); // 更新结果
            right++; // 让下⼀个元素进⼊窗⼝
        }
        return ret;
    }
};