每日一题——无重复字符的最长子串

创业
2025-09-14 10:00:02

无重复字符的最长子串（C语言实现）一、问题描述示例提示二、问题分析1. **问题难点**2. **解决方案** 三、C语言实现1. **使用 `uthash` 的实现**代码实现代码说明 2. **不使用 `uthash` 的实现**代码实现代码说明四、sizeof(s) 的错误问题分析：五、测试用例1. **测试用例 1**2. **测试用例 2**3. **测试用例 3** 六、总结七、参考文献

一、问题描述

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

示例

输入：s = "abcabcbb"

输出：3解释：无重复字符的最长子串是 "abc"，长度为 3。

输入：s = "bbbbb"

输出：1解释：无重复字符的最长子串是 "b"，长度为 1。

输入：s = "pwwkew"

输出：3解释：无重复字符的最长子串是 "wke"，长度为 3。注意，"pwke" 是一个子序列，不是子串。提示 0 <= s.length <= 5 * 10^4s 由英文字母、数字、符号和空格组成。

二、问题分析 1. 问题难点如何高效地判断一个子串中是否存在重复字符？如何在发现重复字符时，快速更新子串的边界？ 2. 解决方案使用滑动窗口技术，通过两个指针 l 和 r 表示子串的左右边界。使用一个辅助数据结构（如哈希表或数组）记录字符的出现情况，以便快速判断字符是否重复。

三、C语言实现 1. 使用 uthash 的实现代码实现 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <uthash.h> typedef struct { char key; // 哈希集合保存的元素 UT_hash_handle hh; // uthash 需要 } hashTable; int lengthOfLongestSubstring(char* s) { int result = 0; int l = 0, r = 0; int n = strlen(s); // 获取字符串的实际长度 hashTable* hashMap = NULL; // 创建一个空哈希集合 hashTable* hashNode; for (r = 0; r < n; r++) { char key = s[r]; HASH_FIND_INT(hashMap, &key, hashNode); if (hashNode == NULL) { // 如果 s[r] 不在集合中，则插入 hashNode = (hashTable*)malloc(sizeof(hashTable)); hashNode->key = key; HASH_ADD_INT(hashMap, key, hashNode); } else { // 如果找到重复字符 // 更新最长子串长度 result = (r - l > result) ? r - l : result; // 从左边界开始逐个删除字符，直到删除重复字符为止 while (s[l] != s[r]) { HASH_DEL(hashMap, hashNode); free(hashNode); l++; HASH_FIND_INT(hashMap, &s[l], hashNode); } l++; // 移动左边界到重复字符的下一个位置 } } // 最后一次更新最长子串长度 result = (r - l > result) ? r - l : result; // 清空哈希表并释放内存 HASH_CLEAR(hh, hashMap); return result; // 返回最长无重复子串的长度 } int main() { char s[100]; printf("请输入字符串: "); scanf("%99s", s); // 防止输入溢出 int result = lengthOfLongestSubstring(s); printf("无重复字符的最长子串长度为: %d\n", result); return 0; } 代码说明

滑动窗口：

使用两个指针 l 和 r 表示子串的左右边界。r 指针用于扩展窗口，l 指针用于收缩窗口。

哈希表：

使用 uthash 库实现哈希表，记录字符的出现情况。当遇到重复字符时，通过 HASH_DEL 删除左边界字符，直到移除重复字符。

字符串长度：

使用 strlen(s) 获取字符串的实际长度，而不是 sizeof(s)。

内存管理：

在删除哈希表节点时，使用 free 释放动态分配的内存。

2. 不使用 uthash 的实现代码实现 #include <stdio.h> #include <stdlib.h> #include <string.h> int lengthOfLongestSubstring(char* s) { int result = 0; int l = 0, r = 0; int cnt[128] = {0}; // ASCII 字符集大小为 128 int n = strlen(s); // 获取字符串的实际长度 for (r = 0; r < n; r++) { char c = s[r]; cnt[c]++; // 增加当前字符的计数 if (cnt[c] > 1) { // 如果当前字符重复 // 更新最长子串长度 result = (r - l > result) ? r - l : result; // 从左边界开始逐个删除字符，直到移除重复字符为止 while (cnt[c] > 1) { cnt[s[l]]--; // 减少左端点字符的计数 l++; // 缩小窗口 } } } // 最后一次更新最长子串长度 result = (r - l > result) ? r - l : result; return result; // 返回最长无重复子串的长度 } int main() { char s[100]; printf("请输入字符串: "); scanf("%99s", s); // 防止输入溢出 int result = lengthOfLongestSubstring(s); printf("无重复字符的最长子串长度为: %d\n", result); return 0; } 代码说明

滑动窗口：

使用两个指针 l 和 r 表示子串的左右边界。r 指针用于扩展窗口，l 指针用于收缩窗口。

字符计数数组：

使用一个大小为 128 的数组 cnt 记录每个字符的出现次数。当遇到重复字符时，通过 cnt[s[l]]-- 减少左边界字符的计数，直到移除重复字符。

字符串长度：

使用 strlen(s) 获取字符串的实际长度，而不是 sizeof(s)。

逻辑优化：

在每次移动 r 指针时，更新 result。在循环结束后，再次更新 result，以确保覆盖所有情况。

四、sizeof(s) 的错误问题分析： sizeof(s) 返回的是指针的大小（通常是 4 或 8 字节），而不是字符串的实际长度。应该使用 strlen(s) 获取字符串的实际长度。

五、测试用例 1. 测试用例 1 输入："abcabcbb"输出：3解释：无重复字符的最长子串是 "abc"，长度为 3。 2. 测试用例 2 输入："bbbbb"输出：1解释：无重复字符的最长子串是 "b"，长度为 1。 3. 测试用例 3 输入："pwwkew"输出：3解释：无重复字符的最长子串是 "wke"，长度为 3。

六、总结

通过滑动窗口技术和字符计数数组，我们可以高效地解决“无重复字符的最长子串”问题。以下是关键点总结：

滑动窗口：

使用两个指针 l 和 r 表示子串的左右边界。r 指针用于扩展窗口，l 指针用于收缩窗口。

字符计数数组：

使用一个大小为 128 的数组记录字符的出现次数。当遇到重复字符时，通过减少左边界字符的计数，直到移除重复字符。

字符串长度：

使用 strlen(s) 获取字符串的实际长度，而不是 sizeof(s)。

逻辑优化：

在每次移动 r 指针时，更新最长子串长度。在循环结束后，再次更新最长子串长度，以确保覆盖所有情况。

七、参考文献 LeetCode：无重复字符的最长子串C语言标准库：<string.h> 和 <stdlib.h>

标签：