专门做搞笑游戏视频网站,wordpress手机验证码登录界面,广商网,烟台城乡住房建设厅网站给定一个字符串 s #xff0c;请你找出其中不含有重复字符的 最长子串的长度。
法一#xff1a;
这道题用到的其实是滑动窗口。
滑动窗口算法是在特定窗口大小的数组或字符串上执行要求的操作。它可以将一部分问题中的嵌套循环转变为一个单循环#xff0c;以此减少时间复…给定一个字符串 s 请你找出其中不含有重复字符的 最长子串的长度。
法一
这道题用到的其实是滑动窗口。
滑动窗口算法是在特定窗口大小的数组或字符串上执行要求的操作。它可以将一部分问题中的嵌套循环转变为一个单循环以此减少时间复杂度。
以字符串为例滑动窗口的思路为
1. 使用双指针中的左右指针技巧初始化left right 0,把[left,right]称为一个窗口
2. 先不断扩大右侧的right指针扩大窗口范围直到窗口中所有的字符串都符合要求 比如要在【A,A,D,D,C,B,A,D,C】中找出现ABC的窗口 在第2步找到【AADDCB】 此时左侧还没动所以从第一个A开始
3. 停止增加右侧指针开始增加左侧left直到窗口中不包含ABC 很遗憾只能移一位保持窗口在【ADDCB】
4. 重复第2步和第3步直到right到达给定字符串的最右侧
》【DDCB】》【DDCBA】》【CBA】》【BA】》【BADC】》【ADC】
//样例输入[A,A,C,B,A],找ABC
public int GetAns(string s)
{int left 0;int right 0;int max 0;int i,j;int length s.Length;bool getSame false;for(i 0;i length;i){//第一遍空循环,right右移变为1//第二遍查找[A,A],发现有同一字符左指针右移右指针也右移,变为[A]//第三遍查找[A,C],无right右移//第四遍查找[A,C,B],无right右移//第五遍, 查找[A,C,B,A],有left右移变为[C,B,A]if(left right){getSame false;for(j 0; j right;j){if(s[j] s[right]){getSame true;break;}}if(getSame){left j1;}} max max (right - left 1) ? (right - left 1): max;right; }return max;
}
法二
看到一个牛逼的大佬用[255]大小数组构建了哈希表以此实现必定无重复
并用ASCII码存储每个字母出现的索引太绝了
public int LengthOfLongestSubstring(string s) {int indexLeft 0;int indexRight 0;int len s.Length;int[] hashMap new int[255];int max 0;while (indexRight len){if (hashMap[s[indexRight]] ! 0){if(hashMap[s[indexRight]] indexLeft)indexLeft hashMap[s[indexRight]];hashMap[s[indexRight]] indexRight 1;}else{hashMap[s[indexRight]] indexRight 1;}max max (indexRight - indexLeft 1) ? (indexRight - indexLeft 1): max;;indexRight;}return max;}
