当前位置：首页 > news >正文

【算法实战】C 语言实现无重复字符的最长子串：滑动窗口 + 哈希表高效解法（附完整可运行代码）

news 2026/5/12 2:44:37

【算法实战】C 语言实现无重复字符的最长子串：滑动窗口 + 哈希表高效解法（附完整可运行代码）

大家好，我是专注编程实战与算法解析的小杨。今天给大家带来经典算法题 ——无重复字符的最长子串的 C 语言实现，这道题是 LeetCode 第 3 题，也是校招、社招面试中的高频考点，考察对「滑动窗口」和「哈希表」核心思想的综合运用。我们会从问题分析入手，拆解算法思路，实现时间复杂度 O (n)、空间复杂度 O (1) 的最优解法，最后附上完整可运行的 C 语言代码，新手也能直接编译测试！

一、先明确问题：无重复字符的最长子串是什么？

问题描述

给定一个字符串，找出其中不包含重复字符的最长连续子串的长度，子串为字符串中连续的字符序列（区别于子序列的非连续）。

示例理解

通过 3 个典型示例，快速掌握问题核心要求：

输入："abcabcbb"→ 输出：3→ 最长无重复子串："abc"
输入："bbbbb"→ 输出：1→ 最长无重复子串："b"
输入："pwwkew"→ 输出：3→ 最长无重复子串："wke"（或"kew"）
输入："abba"→ 输出：2→ 最长无重复子串："ab"或"ba"（易踩坑案例）

问题难点

如何高效判断字符是否重复，且避免暴力枚举的高时间复杂度；
如何动态维护「无重复子串」的范围，处理字符重复时的边界调整；
兼容各种边界场景（全重复、无重复、空字符串、重复字符跨区间等）。

二、算法思路分析：为什么选择「滑动窗口 + 哈希表」？

解决这道题的核心思路是滑动窗口（双指针），配合哈希表实现快速的字符重复判断，两者结合能实现最优的时间复杂度。

1. 暴力枚举法（不可取）

最直观的思路是枚举所有可能的子串，逐一判断是否有重复字符，记录最长长度。

时间复杂度：O (n²)（n 为字符串长度，两层循环枚举子串）；
空间复杂度：O (1)（仅需少量变量）；
问题：当字符串较长时（如 1000 个字符），效率极低，无法通过面试要求。

2. 滑动窗口 + 哈希表（最优解）

核心思想

滑动窗口：用两个指针（左指针start、右指针j）表示一个动态的窗口，窗口内的字符即为「当前无重复子串」，右指针负责扩展窗口，左指针负责在字符重复时收缩窗口，始终保证窗口内无重复字符；
哈希表：用一个数组（替代哈希表，更高效）记录每个字符最后一次出现的索引，实现 O (1) 时间复杂度的重复判断和索引查询。

算法核心步骤

初始化左指针start=0，最大长度maxLen=0，哈希表（数组）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 (1)（哈希表为固定大小的 256 位数组，与字符串长度无关，满足常数空间要求）；
效率：无论字符串多长，都能线性遍历完成，是面试要求的最优解法。

三、核心知识点：哈希表的选择与滑动窗口边界

1. 为什么用数组替代哈希表？

题目中处理的是 ASCII 字符（共 256 种，包括大小写字母、数字、符号等），用一个长度为 256 的整型数组charIndex即可完美替代哈希表：

数组索引：对应字符的 ASCII 码值（如s[j]为'a'，则索引为 97）；
数组值：对应字符最后一次出现的索引，初始值为 - 1（表示未出现）；
优势：数组的访问速度比哈希表更快，实现更简单，无额外开销。

2. 滑动窗口的边界判断（核心避坑点）

判断字符是否重复的条件是charIndex[s[j]] >= start，而非charIndex[s[j]] != -1，这是解决「abba」这类案例的关键：

若仅判断!= -1，当重复字符出现在「当前窗口左侧」时（如abba中第二个a），会错误收缩左指针，导致窗口范围异常；
>= start能确保：仅当字符在当前有效窗口内重复时，才调整左指针，忽略窗口外的历史重复记录。

四、完整可运行代码：C 语言实现最优解

以下是基于「滑动窗口 + 哈希表」的完整 C 语言代码，代码结构清晰、注释详细，兼容所有边界场景，可直接在 Linux/Windows/C 语言编译器（Dev-C++、VS、Clion）中编译运行：

运行

#include <stdio.h> #include <string.h> #include <stdlib.h> // 函数功能：计算无重复字符的最长子串长度 // 入参：s - 输入字符串（ASCII字符） // 出参：返回最长无重复子串的长度 int longestSubstring(char *s) { int n = strlen(s); // 获取字符串长度 if (n == 0) 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 + 1) : maxLen; } return maxLen; } // 主函数：负责输入输出，调用核心函数 int main() { char str[1000]; // 定义字符串数组，支持最长999个字符+结束符 printf("请输入字符串: "); scanf("%s", str); // 读取输入字符串（不含空格，兼容大部分测试场景） int result = longestSubstring(str); // 调用核心函数计算结果 printf("最长无重复子串的长度为: %d\n", result); // 输出结果 return 0; }

五、代码核心细节拆解：逐行理解关键逻辑

1. 头文件与函数声明

运行

#include <stdio.h> // 标准输入输出（printf/scanf） #include <string.h> // 字符串处理（strlen） #include <stdlib.h> // 标准库（可省略，此处为规范）

核心函数longestSubstring：单一职责，仅负责计算最长无重复子串长度，与输入输出解耦，符合模块化设计。

2. 初始化部分

运行

int n = strlen(s); if (n == 0) 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：表示字符从未出现过，是判断字符是否首次出现的基准。

3. 核心遍历与窗口维护

运行

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 + 1) : maxLen; }

这是代码的核心，逐行解析：

charIndex[s[j]] >= start：判断当前字符s[j]是否在当前窗口内重复。s[j]会自动转换为 ASCII 码值作为数组索引，直接获取该字符最后一次出现的索引；
start = charIndex[s[j]] + 1：字符重复时，将左指针移动到重复字符的下一个位置，收缩窗口，保证窗口内无重复；
charIndex[s[j]] = j：无论字符是否重复，都更新其最后一次出现的索引为当前右指针位置，为后续判断做准备；
j - start + 1：计算当前窗口的长度（左闭右闭区间，需 + 1），用三目运算符快速比较并更新最大长度maxLen。

4. 主函数输入输出

运行

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 语言的环境中编译运行，步骤简单。

1. 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 最长无重复子串的长度为: 2

2. Windows 环境编译运行

使用 Dev-C++、Visual Studio、MinGW 等编译器，直接新建 C 语言项目，粘贴代码后点击「编译运行」即可，运行效果与 Linux 一致。

七、常见边界场景测试：避坑指南

这道题的很多错误都出现在边界场景处理，以下是高频测试用例，确保代码兼容所有情况：

输入字符串	预期输出	测试目的
`""`（空）	0	空字符串处理
`"a"`	1	单字符处理
`"aa"`	1	双重复字符
`"abba"`	2	重复字符跨区间（左指针不回退）
`"abcdefg"`	7	无重复字符（全窗口）
`"dvdf"`	3	重复字符后重新扩展窗口
`"1234567890abcdef"`	16	数字 + 字母混合无重复
`"aabccddeeff"`	3	多次重复字符的窗口调整

八、代码优化与扩展：满足更多需求

这份基础代码实现了核心功能，在此基础上可进行简单优化和扩展，适配更多场景。

1. 支持带空格的字符串输入

将main函数中的scanf替换为fgets，并处理换行符：

运行

// 替换原输入代码 char str[1000]; printf("请输入字符串: "); fgets(str, sizeof(str), stdin); // 处理fgets读取的换行符 str[strcspn(str, "\n")] = '\0';

2. 不仅返回长度，还返回最长无重复子串

新增变量记录最长子串的起始和结束索引，遍历结束后截取子串：

运行

// 在longestSubstring函数中新增变量 int maxStart = 0; // 最长子串的起始索引 // 更新maxLen时，同时记录索引 if (j - start + 1 > maxLen) { maxLen = j - start + 1; maxStart = start; } // 函数返回前，可通过maxStart和maxLen截取子串 // 主函数中输出子串 printf("最长无重复子串为: %.*s\n", result, str + maxStart);