剑指offer面试题48(java版):最长不含重复字符的子字符串

布满荆棘的人生 2023-07-07 11:26 12阅读 0赞

### [welcome to my blog][] ###

## 剑指offer面试题48(java版):最长不含重复字符的子字符串 ##

### 题目描述 ###

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
    
    
    示例 1:
    
    输入: "abcabcbb"
    输出: 3 
    解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
    示例 2:
    
    输入: "bbbbb"
    输出: 1
    解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
    示例 3:
    
    输入: "pwwkew"
    输出: 3
    解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
         请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

#### 第一次做; 双指针; 将N^2搜索空间降低为N, 双指针构成了滑动窗口; 双指针的使用模板: 1)移动右指针, 直至滑动窗口不满足条件, 2)此时移动左指针, 直至滑动窗口满足条件 ####

/* 双指针; 将N^2的搜索空间降低为N? 对, 因为right从左到右, left也是从左到右, 所以搜索空间降低为N 使用双指针构建滑动窗口 */
    class Solution { 
        public int lengthOfLongestSubstring(String s) { 
            if(s==null || s.length()==0)
                return 0;
            if(s.length()==1)
                return 1;
            //
            int n = s.length();
            int left=0, right=0;
            //向面试官确认是否只有小写英文字母
            // int[] map = new int[26];
            HashMap<Character, Integer> map = new HashMap<>();
            int max = 0;
            while(right<n){ 
                char ch = s.charAt(right);
                map.put(ch, map.getOrDefault(ch, 0) + 1);
                //滑动窗口中出现重复字符, 需要向右移动left指针, 至少滑动窗口中没有重复字符
                if(map.get(ch) == 2){ 
                    while(left<right && map.get(ch)==2){ 
                        char ch2 = s.charAt(left);
                        map.put(ch2, map.get(ch2)-1);
                        left++;
                    }
                    //here, left==right || map[index]==1
                }
                max = Math.max(right-left+1, max);
                right++;
            }
            return max;
        }
    }

[welcome to my blog]: https://littlehaes.com