核心内容摘要
美国十次啦超级️大导航：解锁你从未见过的美利坚深夜幻境
【算法实战】C 语言实现无重复字符的最长子串滑动窗口 哈希表高效解法附完整可运行代码大家好我是专注编程实战与算法解析的小杨。
今天给大家带来经典算法题 ——无重复字符的最长子串的 C 语言实现这道题是 LeetCode 第 3 题也是校招、社招面试中的高频考点考察对「滑动窗口」和「哈希表」核心思想的综合运用。
我们会从问题分析入手拆解算法思路实现时间复杂度 O (n)、空间复杂度 O (
的最优解法最后附上完整可运行的 C 语言代码新手也能直接编译测试
先明确问题无重复字符的最长子串是什么问题描述给定一个字符串找出其中不包含重复字符的最长连续子串的长度子串为字符串中连续的字符序列区别于子序列的非连续。
示例理解通过 3 个典型示例快速掌握问题核心要求输入abcabcbb→ 输出3→ 最长无重复子串abc输入bbbbb→ 输出1→ 最长无重复子串b输入pwwkew→ 输出3→ 最长无重复子串wke或kew输入abba→ 输出2→ 最长无重复子串ab或ba易踩坑案例问题难点如何高效判断字符是否重复且避免暴力枚举的高时间复杂度如何动态维护「无重复子串」的范围处理字符重复时的边界调整兼容各种边界场景全重复、无重复、空字符串、重复字符跨区间等。
算法思路分析为什么选择「滑动窗口 哈希表」解决这道题的核心思路是滑动窗口双指针配合哈希表实现快速的字符重复判断两者结合能实现最优的时间复杂度。
暴力枚举法不可取最直观的思路是枚举所有可能的子串逐一判断是否有重复字符记录最长长度。
时间复杂度O (n²)n 为字符串长度两层循环枚举子串空间复杂度O (
仅需少量变量问题当字符串较长时如 1000 个字符效率极低无法通过面试要求。
滑动窗口 哈希表最优解核心思想滑动窗口用两个指针左指针start、右指针j表示一个动态的窗口窗口内的字符即为「当前无重复子串」右指针负责扩展窗口左指针负责在字符重复时收缩窗口始终保证窗口内无重复字符哈希表用一个数组替代哈希表更高效记录每个字符最后一次出现的索引实现 O (
时间复杂度的重复判断和索引查询。
算法核心步骤初始化左指针start0最大长度maxLen0哈希表数组charIndex并赋值为 - 1表示字符未出现过右指针j从 0 开始遍历字符串逐个处理字符s[j]判断当前字符s[j]是否在当前窗口内重复若charIndex[s[j]] start说明字符在窗口内已存在将左指针start移动到charIndex[s[j]] 1收缩窗口排除重复字符更新哈希表记录当前字符s[j]的最新索引charIndex[s[j]] j计算当前窗口的长度j - start 1更新最大长度maxLen遍历结束后maxLen即为答案。
关键优势时间复杂度O (n)仅需一次遍历每个字符仅被左、右指针各访问一次空间复杂度O (
哈希表为固定大小的 256 位数组与字符串长度无关满足常数空间要求效率无论字符串多长都能线性遍历完成是面试要求的最优解法。
核心知识点哈希表的选择与滑动窗口边界
为什么用数组替代哈希表题目中处理的是 ASCII 字符共 256 种包括大小写字母、数字、符号等用一个长度为 256 的整型数组charIndex即可完美替代哈希表数组索引对应字符的 ASCII 码值如s[j]为a则索引为 97数组值对应字符最后一次出现的索引初始值为 - 1表示未出现优势数组的访问速度比哈希表更快实现更简单无额外开销。
滑动窗口的边界判断核心避坑点判断字符是否重复的条件是charIndex[s[j]] start而非charIndex[s[j]] ! -1这是解决「abba」这类案例的关键若仅判断! -1当重复字符出现在「当前窗口左侧」时如abba中第二个a会错误收缩左指针导致窗口范围异常 start能确保仅当字符在当前有效窗口内重复时才调整左指针忽略窗口外的历史重复记录。
完整可运行代码C 语言实现最优解以下是基于「滑动窗口 哈希表」的完整 C 语言代码代码结构清晰、注释详细兼容所有边界场景可直接在 Linux/Windows/C 语言编译器Dev-C、VS、Clion中编译运行c运行#include stdio.h #include string.h #include stdlib.h // 函数功能计算无重复字符的最长子串长度 // 入参s - 输入字符串ASCII字符 // 出参返回最长无重复子串的长度 int longestSubstring(char *s) { int n strlen(s); // 获取字符串长度 if (n
return 0; // 边界处理空字符串直接返回0 int maxLen 0; // 记录最长无重复子串长度初始为0 int start 0; // 滑动窗口左指针指向当前无重复子串的起始位置 int charIndex[256]; // 哈希表数组记录每个字符最后一次出现的索引ASCII共256种字符 // 初始化哈希表所有字符初始化为-1表示未出现过 for (int i 0; i 256; i) { charIndex[i] -1; } // 右指针j遍历字符串扩展滑动窗口 for (int j 0; j n; j) { // 核心判断当前字符在当前窗口内重复调整左指针到重复字符的下一个位置 if (charIndex[s[j]] start) { start charIndex[s[j]] 1; } // 更新哈希表记录当前字符的最新索引 charIndex[s[j]] j; // 计算当前窗口长度更新最大长度三目运算符简化判断 maxLen (j - start 1 maxLen) ? (j - start
: maxLen; } return maxLen; } // 主函数负责输入输出调用核心函数 int main() { char str[1000]; // 定义字符串数组支持最长999个字符结束符 printf(请输入字符串: ); scanf(%s, str); // 读取输入字符串不含空格兼容大部分测试场景 int result longestSubstring(str); // 调用核心函数计算结果 printf(最长无重复子串的长度为: %d\n, result); // 输出结果 return 0; }
代码核心细节拆解逐行理解关键逻辑
头文件与函数声明c运行#include stdio.h // 标准输入输出printf/scanf #include string.h // 字符串处理strlen #include stdlib.h // 标准库可省略此处为规范核心函数longestSubstring单一职责仅负责计算最长无重复子串长度与输入输出解耦符合模块化设计。
初始化部分c运行int n strlen(s); if (n
return 0; int maxLen 0; int start 0; int charIndex[256]; for (int i 0; i 256; i) { charIndex[i] -1; }strlen(s)获取字符串有效长度注意不包含结束符\0空字符串判断直接返回 0避免后续无效遍历charIndex[256]固定大小数组覆盖所有 ASCII 字符无需动态分配内存初始化-1表示字符从未出现过是判断字符是否首次出现的基准。
核心遍历与窗口维护c运行for (int j 0; j n; j) { if (charIndex[s[j]] start) { start charIndex[s[j]] 1; } charIndex[s[j]] j; maxLen (j - start 1 maxLen) ? (j - start
: maxLen; }这是代码的核心逐行解析charIndex[s[j]] start判断当前字符s[j]是否在当前窗口内重复。
s[j]会自动转换为 ASCII 码值作为数组索引直接获取该字符最后一次出现的索引start charIndex[s[j]] 1字符重复时将左指针移动到重复字符的下一个位置收缩窗口保证窗口内无重复charIndex[s[j]] j无论字符是否重复都更新其最后一次出现的索引为当前右指针位置为后续判断做准备j - start 1计算当前窗口的长度左闭右闭区间需 1用三目运算符快速比较并更新最大长度maxLen。
主函数输入输出c运行char str[1000]; printf(请输入字符串: ); scanf(%s, str); int result longestSubstring(str); printf(最长无重复子串的长度为: %d\n, result);定义str[1000]支持最长 999 个字符的输入满足日常测试需求scanf(%s, str)读取不含空格的字符串若需支持空格可替换为fgets(str, sizeof(str), stdin)需处理换行符函数调用解耦主函数仅负责输入输出核心算法逻辑在longestSubstring中便于后续修改和扩展。
编译与运行多环境测试Linux/Windows这份代码无第三方依赖仅使用 C 语言标准库可在所有支持 C 语言的环境中编译运行步骤简单。
Linux 环境编译运行步骤 1保存代码将代码保存为longest_substring.c文件名自定义后缀为.c。
步骤 2编译代码打开 Linux 终端进入代码所在目录执行gcc编译命令bash运行gcc longest_substring.c -o longest_substring无输出表示编译成功当前目录生成可执行程序longest_substring若有编译错误检查代码是否复制完整、是否有语法错误如少分号、括号不匹配。
步骤 3运行程序bash运行./longest_substring测试示例运行结果plaintext# 测试1输入abcabcbb 请输入字符串: abcabcbb 最长无重复子串的长度为: 3 # 测试2输入bbbbb 请输入字符串: bbbbb 最长无重复子串的长度为: 1 # 测试3输入pwwkew 请输入字符串: pwwkew 最长无重复子串的长度为: 3 # 测试4输入abba易踩坑案例 请输入字符串: abba 最长无重复子串的长度为:
Windows 环境编译运行使用 Dev-C、Visual Studio、MinGW 等编译器直接新建 C 语言项目粘贴代码后点击「编译运行」即可运行效果与 Linux 一致。
常见边界场景测试避坑指南这道题的很多错误都出现在边界场景处理以下是高频测试用例确保代码兼容所有情况输入字符串预期输出测试目的空0空字符串处理a1单字符处理aa1双重复字符abba2重复字符跨区间左指针不回退abcdefg7无重复字符全窗口dvdf3重复字符后重新扩展窗口1234567890abcdef16数字 字母混合无重复aabccddeeff3多次重复字符的窗口调整
代码优化与扩展满足更多需求这份基础代码实现了核心功能在此基础上可进行简单优化和扩展适配更多场景。
支持带空格的字符串输入将main函数中的scanf替换为fgets并处理换行符c运行// 替换原输入代码 char str[1000]; printf(请输入字符串: ); fgets(str, sizeof(str), stdin); // 处理fgets读取的换行符 str[strcspn(str, \n)] \0;
不仅返回长度还返回最长无重复子串新增变量记录最长子串的起始和结束索引遍历结束后截取子串c运行// 在longestSubstring函数中新增变量 int maxStart 0; // 最长子串的起始索引 // 更新maxLen时同时记录索引 if (j - start 1 maxLen) { maxLen j - start 1; maxStart start; } // 函数返回前可通过maxStart和maxLen截取子串 // 主函数中输出子串 printf(最长无重复子串为: %.*s\n, result, str maxStart);
兼容 Unicode 字符如中文若需处理中文、Emoji 等 Unicode 字符需将哈希表改为struct结构体或使用 C 语言的哈希表库同时将字符处理改为按 UTF-8 编码解析时间复杂度仍可保持 O (n)。
九、
总结这道题的核心考点与收获
面试核心考点对「滑动窗口双指针」算法思想的理解和应用对哈希表或数组替代的高效使用实现 O (
时间复杂度的查询边界场景的处理能力如「abba」这类易踩坑案例代码的模块化设计和可读性算法与输入输出解耦。
学习收获掌握滑动窗口算法的核心思想动态维护窗口范围用双指针减少重复计算该算法可解决大量字符串 / 数组的子问题如最长子数组、最小覆盖子串等学会用数组替代哈希表的技巧在字符范围固定时数组比哈希表更高效、更简单培养边界场景思维算法题不仅要实现基本功能还要兼容所有极端情况积累经典算法题的解题模板滑动窗口 哈希表的组合可直接套用在类似的子串 / 子数组问题中。
延伸学习掌握这道题后可继续学习相关的滑动窗口算法题巩固思路LeetCode 76最小覆盖子串困难滑动窗口进阶LeetCode 209长度最小的子数组中等数组版滑动窗口LeetCode 438找到字符串中所有字母异位词中等滑动窗口 字符计数。
这份无重复字符的最长子串解法是 C 语言算法实战的经典案例既考察基础语法又考察算法思想希望大家能吃透思路而非死记代码。
真正掌握后面对同类问题就能举一反三