leetcode-3:最长无重复字串_leetcode 3

思路：滑动窗口+大小为257的整型数组记录子串元素的位置/哈希表
位置数组：0表示不在子串中，非0表示位置
i 起始位置
j 结束位置

int lengthOfLongestSubstring(string s) {
        int length = s.size();
        if (length == 0) return 0;

        int pos[257] = { 0 };//存储子串中各个元素的位置，如果是0，则不在子串中
        int max_len = 1;//最大不重复子串长度

        for (int i = 0, j = 0; i < length && j < length;)//i前标，b后边
        {
            if (pos[s[j]] == 0) {//子串中无元素
                pos[s[j]] = j + 1;
                j++;

            }
            else {//子串中有元素，i后移到重复元素的后一个位置，j往后移一位，i到后来的位置的中间元素的位置清0
                for (; i < pos[s[j]]+1; i++)
                    pos[s[i]] = 0;
                pos[s[j]] = j;
                j++;
            }
            max_len = max(max_len, j - i);
        }
        return max_len;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24