给定一个字符串 s，i请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1:
输入:s=“abcabcbb”
输出:3
解释:因为无重复字符的最长子串是"abc"，所以其长度为 3.
示例 2:
输入:s =“bbbbb”
输出:1
解释:因为无重复字符的最长子串是"b"所以其长度为 1。
示例 3:
输入:s =“pwwkew’
输出:3
解释:因为无重复字符的最长子串是"wke"，所以其长度为 3.
请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。
提示:
0<= s.length <= 5*104
s由英文字母、数字、符号和空格组成
2024年9月5日，第二道hot100中难度题。
解题思路：临时空间用于存储子串，临时空间不停地更新最新的最长子串，直到s全部遍历。将最终子串拷贝到最后的结果中。
需要考虑的点：1）s遍历结束都没有重复，需要在for结束后拷贝整个临时数组；2）有重复，则需要处理临时数组，找到临时数组中哪个字符开始重复，然后将后面的所有字符都前移，然后与ret中的子串判断，看是否需要更新ret。（最开始直接将字符前移到s出现重复的字符处，会导致子串漏掉）
我的代码中存在的问题：1）不需要使用calloc，只需要使用临时数组即可；2）所有的ASCII字符只有128个，所有数组大小为128；3）时间复杂度为O(n²)；4）空间复杂度也多了一倍！用到了两个临时数组；
改进法：使用窗口滑动法；时间复杂度为O(n);
用时：第一次看题+编码耗时30分钟，vs调试耗时27+60+60；大致耗时3小时。
int lengthOfLongestSubstring(char* s)
{char* sRet = (char*)calloc(129, sizeof(char));char* sTmp = (char*)calloc(129, sizeof(char));if (sRet == NULL || sTmp == NULL || s == NULL)return 0;int iLastLen = 0, iSlen = strlen(s);bool bRepeat = 0;for (int i = 0; i < iSlen; i++){bRepeat = 0;int iCurTmpLen = strlen(sTmp);//判断当前s字符串的字符是否与sTmp子串有重复int j = 0;for (j = 0; j < iCurTmpLen; j++){if (sTmp[j] == s[i]){bRepeat = 1;break;}}sTmp[iCurTmpLen++] = s[i];if (bRepeat){if (iCurTmpLen > iLastLen){memcpy(sRet, sTmp, iCurTmpLen-1);iLastLen = iCurTmpLen-1;}int iTmp = 0;for (int k = j+1; k < iCurTmpLen; k++){sTmp[iTmp++] = sTmp[k];}//清空sTmp后面的垃圾数据memset(sTmp+ iTmp, 0, 129-iTmp);}}memcpy(sRet, sTmp, strlen(sTmp));iLastLen = strlen(sRet);free(sTmp);free(sRet);return iLastLen;
}
chatgpt代码（滑动窗口法）：
int lengthOfLongestSubstring(char* s) {int n = strlen(s);if (n == 0) return 0;int maxLength = 0;int start = 0; // 滑动窗口的起点int lastIndex[128]; // 存储字符上次出现的位置，假设字符集为ASCII（共128个字符）// 初始化 lastIndex 数组为 -1，表示字符还没有出现过for (int i = 0; i < 128; i++) {lastIndex[i] = -1;}// 遍历字符串for (int i = 0; i < n; i++) {char currentChar = s[i];// 如果当前字符在滑动窗口内已经出现过，移动窗口的起点if (lastIndex[currentChar] >= start) {start = lastIndex[currentChar] + 1;}// 更新字符的最新出现位置lastIndex[currentChar] = i;// 更新最大长度int currentLength = i - start + 1;if (currentLength > maxLength) {maxLength = currentLength;}}return maxLength;
}
