大秦帝国之裂变,海子的诗,痔疮的症状-瓦村电影院-瓦伦西亚电影爱好者协会-影讯发布

频道:国内时事 日期: 浏览:138

         LeeCode第三题,难度中等



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


示例1:

输入: "abcabcbb"输出: 3 解说: 由于无重复字符的最长子串是 "abc",所以其长度为 3。

示例2:

输入: "bbbbb"输出: 1解说: 由于无重复字符的最长子串是 "b",所以其长度为 1。

示例3:

输入: "pwwkew"输出: 3解说: 由于无重复字符的最长子串是 "wke",所以其长度为 3。     请注意,你的答案有必要是 子串 的长度,"pwke" 是一个子序列,不是子串。



01

暴力破解


遍历每个字符 x ,顺次求出 x 后面无重复子串的长度,取最大值回来。

public int lengthOfLongestSubstring(String s) {    int n = s.length();    int max = 0;    char[] arr = s.toCharArray();    for(int i = 0; i < n; i++){        max = Math.max(getLength(i, n, arr), max);    }    return max;}
//用set去重,获取子串长度 private int getLength(int start,int n,char[] arr){ Set<Character> set = new HashSet<>(); for(int j = start; j < n; j++){ if(set.contains(arr[j])){ return set.size(); } set.add(arr[j]); } return set.size();}


履行代码:

输入"abcabcbb"输出3预期成果3


提交代码:

履行用时 : 131 ms, 在Longest Substring Without Repeating CharactersJava提交中打败了20.34% 的用户内存耗费 : 86.1 MB, 在Longest Substring Without Repeating CharactersJava提交中打败了8.42% 的用户


剖析:

    功率一言难尽,可是逻辑好了解:求出每一种成果,两两比较得出最大值。


时刻复杂度:O(n²)。

空间复杂度:O(n)。



02

滑动窗口


界说两个指针 i 和 j ,j 先往前走,假如当时元素已存在map中,则将 i 的方位变更到重复元素的方位,最终将当时元素放到map中。

public int lengthOfLongestSubstring(String s) {    int ans = 0;    //i指针    int i = 0;    Map<Character, Integer> map = new HashMap<>();    //j指针,j先走    for(int j = 0; j < s.length(); j++ ){        //假如元素重复,则改动 i 的方位。        if(map.containsKey(s.charAt(j))){            i = Math.max(i, map.get(s.charAt(j)));        }        ans = Math.max(ans, j + 1 - i);        map.put(s.charAt(j), j + 1);    }    return ans;}


履行代码:

输入"abcabcbb"输出3预期成果3


提交代码:

履行用时 : 22 ms, 在Longest Substring Without Repeating CharactersJava提交中打败了83.85% 的用户内存耗费 : 36.6 MB, 在Longest Substring Without Repeating CharactersJava提交中打败了96.75% 的用户



剖析:

    功率瞬间提上去。


时刻复杂度:O(n)。最差的状况,i 和 j 将一切的元素都走一遍O(2n)=(n),如“aaaaa”。

空间复杂度:O(n)。



原题链接:

https://leetcode.com/problems/longest-substring-without-repeating-characters/

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/




点击留言~