leetcode03

无重复字符的最长子串

给定一个字符串，找出其中不含有重复字符的最长的子串。并返回其长度。

例：

输入的是: String s = “abcabcbb”

则最长子串是 “abc” 输出3

双指针，一个指针标记起始位置，一个指针标记结束位置。

对于例子来说，假设标记起始位置的指针是 start，遍历字符串，并确定start的值，最开始为0，将字符串中每个字符的下标记录下来，因为在确定start的值时，有可能这个字符出现过，如果出现过，则让start从上一次出现的下一个的位置，开始进行扫描，并且每一次循环，都可以得到当前的子串长度为 i-start+1。

整个遍历过程中，我们如何得到最大长度，假设最终长度是res，只需要取出当前循环得到的长度和原先长度中的最大值就可以了。如何记录字符串元素的下标。我们知道字符在java内存是通过ASCII的方式，以整型来进行存储的。

根据ASCII对照表，选择一个int数组，大小为128就可以了。

可能说的不是很清楚，记录下代码，避免忘记。

class Solution {
    public int lengthOfLongestSubstrinh(String s) {
        //非空判断
        if (s == null || s.length() == 0) return -1;
        //创建一个int数组记录每个元素上一次出现的位置
        int[] last = new int[128];
        //初始化这个数组，让所有的元素值都为-1
        for (int i = 0; i < last.length; i++) {
            last[i] = -1;
        }
        
        //记录最大长度
        int result = 0;
        //起始位置
        int start = 0;
        //得到字符串的长度
        int length = s.length();
        
        for (int i = 0; i < length; i++) {
            //取出字符
            int index = s.charAt(i);
            start = Math.max(start, last[index] + 1); //如果字符出现过，就从下一个作为起始位置
            result = Math.max(result, i - start + 1); //得到最大长度
            last[index] = i; //记录每一个字符的下标
        }
        
        return result;
    }
}

对滑动窗口的理解不是很清晰。。。继续努力！

其实leetcode官方给出的解答还是比较清晰的，使用一个set集合来记录字符。滑动窗口，通过两个指针，左指针标记起始位置，右指针进行滑动，当下标不越界并且在集合中没有当前字符时，不断地往set集合中加入元素，而字符出现过后，则退出循环，让左指针指向下一个元素，并且将前一个字符删掉，然后再进行循环，最后得到最大长度。

搬运一下官方代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。