LeetCode刷题第3题（C#）

给定一个字符串 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 = j+1;}}  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;}