3. Longest Substring Without Repeating Characters [Medium]

3. Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Constraints:

• 0 <= s.length <= 5 * 10^4
• s consists of English letters, digits, symbols and spaces.

Example

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

思路

• 是求连续子串不是子序列
• 左右指针来截取字符串，右指针每要添加进一个字符时，先看一下当前截取字符串中是否已存在，如果存在就左指针移一位

题解

• 无脑快速AC

    public int lengthOfLongestSubstring(String s) {
        int left, right, result;
        left = right = result = 0;
        String temp;

        while (right < s.length()) {
	    // 获取右指针字符，也就是待插入字符
            String cur = String.valueOf(s.charAt(right));
	    // 截取当前左指针到右指针前1位的字符串
            temp = s.substring(left, right);
	    // 当前子串中包含待插入字符，移动左指针
            if (temp.contains(cur)) {
                left++;
            } else {
		// 直到符合条件，那就算出当前子串长度
                result = Math.max(result, right - left + 1);
                right++;
            }
        }
        return result;
    }

• 优化

    public int lengthOfLongestSubstring(String s) {
        int result, left;
	// 利用Set特性来简化，不依靠截取字符串函数
        HashSet<Character> record = new HashSet<>();
        result = left = 0;

        char[] data = s.toCharArray();
	// i就可以当作右指针
        for (int i = 0; i < data.length; i++) {
	    // 如果Set中已存在当前待插入元素，返回false，那就从最左边开始移出，直到成功插入，最坏情况就是Set被清空，然后当前i成为Set中唯一元素
            while (!record.add(data[i])) {
                record.remove(data[left]);
                left++;
            }
            result = Math.max(result, i - left + 1);
        }
        return result;
    }