leetcode03-无重复字符的最长子串

比眉伴天荒 2024-04-17 14:36 54阅读 0赞

*  [无重复字符的最长子串][Link 1]
    
     *  [题目描述][Link 2]
     *  [code][]

# 无重复字符的最长子串 #

## 题目描述 ##

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

示例 1:

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

## code ##

package com.wangyg.leetcode;
    
    import org.junit.Test;
    
    import java.util.HashSet;
    import java.util.Set;
    import java.util.jar.JarEntry;
    
    public class Test03 {
        @Test
        public void test() {
            String s = "pwwkew";
            Solution03 sl = new Solution03();
            System.out.println(sl.lengthOfLongestSubstring3(s));
        }
    }
    
    class Solution03 {
        //最长子序列
        //缺陷：复杂度太高,时间复杂度为O(n^3), 但其实有很多重复无用的判断，可以进行优化
        public int lengthOfLongestSubstring(String s) {
            if (s == null || "".equals(s.trim())) {
                return 0;
            }
            int lenght = 0;
            for (int i = 0; i < s.length(); i++) {
                for (int j = i + 1; j < s.length(); j++) {
                    if (isDuplicate(s, i, j)) {
                        lenght = lenght < j - i + 1 ? j - i + 1 : lenght;
                    }
                }
            }
            return lenght;
        }
    
        private boolean isDuplicate(String s, int left, int right) {
            //使用set进行去重
            Set<Character> set = new HashSet<>();
            for (int i = left; i <= right; i++) {
                if (set.contains(s.charAt(i))) {
                    return false;
                } else {
                    set.add(s.charAt(i));
                }
            }
            return true;
        }
    
        //无重复子串的最大长度
        public int lengthOfLongestSubstring2(String s) {
            int maxLength = 0;
            char[] chars = s.toCharArray(); //转为数组
            int leftIndex = 0;//左侧索引
            for (int i = 0; i < chars.length; i++) {
                for (int index = leftIndex; index < i; index++) {
                    if (chars[index] == chars[i]) {
                        maxLength = Math.max(maxLength, i - leftIndex);
                        leftIndex = index + 1;
                        break;
                    }
                }
            }
            return Math.max(chars.length - leftIndex, maxLength);
        }
    
        /*
            思路：
           暴力方法中，反复检查一个子字符串是否含有重复的字符，但这是没有必要的，
           如果从索引 i 到 索引j-1之间的 子字符串 sij-1 已经没有重复的元素,
           我们只需要检查s[j] 对应的字符是否已经存在于子字符串sij 中
    
           检查一个字符是否存在于一个子字符串中，可以检查整个子字符串，这将产生一个
           复杂度为O(n^2)的算法，但我们可以做得更好
    
           通过使用hashset作为滑动窗口，可以用O(1)的时间来完成对字符是否在当前的
           子字符串中的检查
    
            滑动窗口是数组/子字符串问题中常用的抽象概念, 窗口通常是在数组/字符串中
            由开始和结束索引 定义的一系列元素的集合，即 [i, j)[i,j)
            （左闭，右开）
            而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。
            例如，我们将 [i, j)[i,j) 向右滑动 11 个元素，则它将变为 [i+1, j+1)[i+1,j+1)
            （左闭，右开）。
    
            回到我们的问题，我们使用 HashSet 将字符存储在当前窗口 [i, j)[i,j)
            （最初 j = ij=i）中。 然后我们向右侧滑动索引 jj，如果它不在 HashSet 中，
            我们会继续滑动 jj。直到 s[j] 已经存在于 HashSet 中。
            此时，我们找到的没有重复字符的最长子字符串将会以索引 ii 开头。
            如果我们对所有的 ii 这样做，就可以得到答案。
           */
        public int lengthOfLongestSubstring3(String s) {
            int n = s.length();
            Set<Character> set = new HashSet<>(); //使用hashset定义一个滑动窗口
            int ans = 0, i = 0, j = 0; // i j
            while (i < n && j < n) { //滑动窗口限制, n为字符串的长度
                // try to extend the range [i, j]
                if (!set.contains(s.charAt(j))) { //如果不包含右侧元素，
                    set.add(s.charAt(j++)); //则添加到滑动窗口中
                    ans = Math.max(ans, j - i); //ans = ans 和j-i最大值
                } else { //否则删除左侧i 位置元素，然后向后移动一个位置
                    set.remove(s.charAt(i++));
                }
            }
            return ans;
        }
    
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTAxMDIzNDk5MQ_size_16_color_FFFFFF_t_70][]

[Link 1]: https://note.youdao.com/md/preview.html?file=%2Fyws%2Fapi%2Fpersonal%2Ffile%2F2AE002698327492CBD497E3AD0BB1E7F%3Fmethod%3Ddownload%26read%3Dtrue%26shareKey%3D0eaf713ab7252c2d823e80b9011d6d13#%E6%97%A0%E9%87%8D%E5%A4%8D%E5%AD%97%E7%AC%A6%E7%9A%84%E6%9C%80%E9%95%BF%E5%AD%90%E4%B8%B2
[Link 2]: https://note.youdao.com/md/preview.html?file=%2Fyws%2Fapi%2Fpersonal%2Ffile%2F2AE002698327492CBD497E3AD0BB1E7F%3Fmethod%3Ddownload%26read%3Dtrue%26shareKey%3D0eaf713ab7252c2d823e80b9011d6d13#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0
[code]: https://note.youdao.com/md/preview.html?file=%2Fyws%2Fapi%2Fpersonal%2Ffile%2F2AE002698327492CBD497E3AD0BB1E7F%3Fmethod%3Ddownload%26read%3Dtrue%26shareKey%3D0eaf713ab7252c2d823e80b9011d6d13#code
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTAxMDIzNDk5MQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190827193850886.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTAxMDIzNDk5MQ==,size_16,color_FFFFFF,t_70