剑指 Offer II 016. 不含重复字符的最长子字符串(中等)

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

示例 1: 输入: s = "abcabcbb"

            输出: 3

            解释:因为无重复字符的最长子字符串是"abc",所以其长度为 3。

解题思路:使用滑动窗口法,定义两个指针,left和right,left表示窗口的左侧下标,right表示窗口的右侧下标,窗口大小为right-left+1。

                   定义一个hashMap<Character, Integer>,key是s内的各字符,value是key对应的下标。

                  right一直++, 每+一次,就在hashMap查找是否有重复字符,并把right的字符加入hashMap,直到窗口内出现了重复字符,这时候令left=该字符对应的原下标+1,并在hashMap中删除left之前的所有字符对应数据,并把right的字符加入hashMap。 直到right=s.length()-1,遍历完成。

                    返回窗口的最大大小。

public int lengthOfLongestSubstring(String s) {

        Map<Character, Integer> hashTable = new HashMap<>();   // 定义一个hashMap 来存储是否有重复的字符

        int left = 0;

        int right = 0;

        int max = 0;

        while (right<s.length()) {

            if(hashTable.get(s.charAt(right)) != null) { // 如果hashMap中有重复字符

                int temp = left;

                left = hashTable.get(s.charAt(right)) + 1;// 令left=该字符对应的原下标+1

                for(int i=temp; i<left-1; i++) {

                    hashTable.remove(s.charAt(i)); // 在hashMap中删除left之前的所有字符对应数据

                }

            }

            hashTable.put(s.charAt(right), right);// 把right的字符加入hashMap

            max = Math.max(max, right-left+1); // 返回窗口的最大大小

            right++;

        }

        return max;

    }

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容