LeetCode_03_LongestSubstringWithoutRepeatingCharacters

LeetCode

发布日期: 2022-01-28

更新日期: 2022-02-19

文章字数: 977

阅读时长: 3 分

阅读次数:

1. question：无重复字符的最长子串（中等）

question: 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

示例 1:

1
2
3

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

1 2	0 <= s.length <= 5 * 104 s 由英文字母、数字、符号和空格组成

2. answers

思路：

这道题涉及到子串长度，可以采用双指针的方法来做。

无限不重复子串，首先要保留一个指针，用于遍历字符串；另外需要一个指针，保存当前子串的下标，当出现重复字符的时候，即代表子串结束，计算当前子串的长度。

比较之前保存的最长长度和当前子串的长度，取最大值保存。更新新子串的起始下标，继续遍历直到结束。

注意，新子串的起始下标：

必须是当前最新重复字符的后面的字符；

代码如下所示：

public class Solution_0003 {

    public static int lengthOfLongestSubstring(String s) {

        // 将字符串转换成数组，便于后续根据下标访问
        char[] chars = s.toCharArray();

        // 保存 长度 和 计算长度的起始下标，初始化均为0.
        int answer = 0;
        int tempStart = 0;

        // 创建map，存储遍历过的元素，<元素, 最新的下标>。
        Map<Character, Integer> map = new HashMap<>();

        // 遍历字符串，只要没有重复的元素，就将其添加到map中；如果有重复的元素，则起始下标向后移动一位，并更新重复元素的最新下标。
        for (int i = 0; i < s.length(); i++) {

            if(map.containsKey(chars[i])){

                // 包含重复元素，说明此时获得了一个子串，比较当前子串的长度和之前的答案，取最大的值为答案。
                answer = Math.max(answer, i - tempStart);

                // 包含重复元素，当前子串结束，记录下一个重复子串的起始位置
                // 下一个子串的起始位置是 map保存的当前重复字符的下一个字符。

                // 但是Map是无序的，无法通过当前重复元素找到Map中的下一个字符。
                // 首先可以肯定的一点是：Map中保留的是不重复的字符，所以Map中保留的一定是字符串中相邻的元素
                // 我们可以通过当前字符获取到其在字符串中的下标，然后通过下标和字符串获取到下一个字符

                // 注意，要考虑 “abba”这种情况，当遍历a的时候，当时的子串是b，即起始下标是b，
                // 那么遍历a的时候，更新下标，实际上就不单纯是a的下一个元素了，
                // 应该是 a的下一个元素 和 当前起始下标的最大值。
                tempStart = Math.max(map.get(chars[i]) + 1, tempStart);

            }

            // 将元素添加到map中
            map.put(chars[i], i);

        }

        // 最后遍历完计算一遍长度，因为最后可能没有重复字符出现
        answer = Math.max(answer, s.length() - tempStart);

        return answer;
    }

    public static void main(String[] args) {
//        String s = "abcabcbb";
//        String s = "bbbbb";
//        String s = "pwwkew";
//        String s = "abcad";
        String s = "abba";

        int subLength = lengthOfLongestSubstring(s);
        System.out.println(subLength);

    }
}