Leecode-3 Longest Substring Without Repeating Char

luzhuqun 發布于2019-08-16 13:49 / 699人閱讀

摘要：題目解析題目含義很簡單，即求出沒有字符重復的子字符串的長度。例如很明顯就是個由完全重復字符組成的字符串，所以它的答案長度為。所以綜合來看該算法的效率為。

題目

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

解析

題目含義很簡單，即求出沒有字符重復的子字符串的長度。例如bbbbb很明顯就是個由完全重復字符組成的字符串，所以它的答案長度為1。

解法1 : 遍歷字符串構成無重復字符字符串

最簡單的方法就是通過遍歷字符串的每一個字符，循環的構造子字符串，遇到重復字符便停止，然后得出最長長度的那個字符串。

    public static int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        for(int index = 0 ; index=0){
                    if(temp.length()>maxLength)
                        maxLength = temp.length();
                    break;
                }else{
                    temp.append(s.charAt(buffer));
                }
            }
            // 如果該子串的長度大于當前最大長度，那么替換為最長長度
            if(temp.length()>maxLength){
                maxLength = temp.length();
            }
        }
        return maxLength;
    }

這個方法非常好理解，但是唯一的問題就是效率非常低,在外層有兩層循環，在尋找字符操作時(temp.indexOf(currStr))也要循環一遍，所以該算法的復雜度為O(n^3)

解法2 滑動構造子串

    public static int lengthOfLongestSubstring(String s){
        // 非空校驗
        if(s==null || s.isEmpty()){
            return 0;
        }
        int length = s.length();

        // 定義滑動標志位:indexOne，indexTwo s[indexOne]~s[indexTwo]之間的字符串組成一個不重復字符的子                
        // 串
        int indexOne = 0 , indexTwo = 0;
        int maxLength = 0;
        Set set = new HashSet<>();
        while(indexOne < length && indexTwo < length){

            // 如果set不包含新字符
            if(!set.contains(s.charAt(indexTwo))){

                // 那么indexTwo++ ，同時將新字符添加到set中
                set.add(s.charAt(indexTwo++));

                // 當前子串長度為 indexTwo - indexOne
                maxLength = Math.max(maxLength , indexTwo - indexOne);
            }else{
                set.remove(s.charAt(indexOne++));
            }
        }
        return maxLength;
    }

滑動構造子串的意思即通過兩個索引indexOne，indexTwo動態構造子串，如果下一個字符沒重復，那么indexTwo+1，如果下一個字符已重復，那么indexOne+1。
在最好的情況下，例如輸入"abcde"的時候，下一個字符一直是新的字符，那么indexTwo可以一直+1，直到字符串被遍歷完，這時候的效率為O(n)。
在最差的情況下，例如輸入"bbbbb"的時候，下一個字符一直是重復字符，那么程序一直執行indexTwo+1后indexOne+1的循環，也即indexOne和indexTwo分別遍歷了一遍了字符串，那么這時候的效率為O(2n)。
所以綜合來看該算法的效率為O(n)。

云服務器 GPU云服務器 Repeating Without Longest Substring

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/72391.html

[Leetcode]Longest Substring Without Repeating Char

摘要：解題思路本題借助實現。如果字符未出現過，則字符，如果字符出現過，則維護上次出現的遍歷的起始點。注意點每次都要更新字符的位置最后返回時，一定要考慮到從到字符串末尾都沒有遇到重復字符的情況，所欲需要比較下和的大小。 Longest Substring Without Repeating CharactersGiven a string, find the length of the lon...

awesome23 2019-08-16 10:26 評論0 收藏0
LeetCode——Longest Substring Without Repeating Char

摘要：原問題我的沙雕解法無重復字母存在重復字母挨打最暴力的無腦解法，耗時。。。原問題 Given a string, find the length of the?longest substring?without repeating characters. Example 1: Input: abcabcbb Output: 3 Explanation: The answer is a...

forsigner 2019-08-26 13:31 評論0 收藏0
[LeetCode] Longest Substring Without Repeating Cha

摘要：建立數組，存儲個字符最近一次出現的位置。首次出現某字符時，其位置標記為，并用無重復字符計數器記錄無重復字符的長度，再在更新其最大值。循環完整個字符串后，返回最大值。 Problem Given a string, find the length of the longest substring without repeating characters. Examples: Given ...

CoderStudy 2019-08-14 15:48 評論0 收藏0
leetcode 3 Longest Substring Without Repeating Cha

摘要：題目詳情題目要求輸入一個字符串，我們要找出其中不含重復字符的最長子字符串，返回這個最長子字符串的長度。對于字符串中的每一個字符，先判斷中是否已經存在這個字符，如果不存在，直接將添加到，如果已存在，則新的字符串就從不含前一個字符的地方開始。題目詳情 Given a string, find the length of the longest substring without repe...

xcold 2019-08-15 14:21 評論0 收藏0
[Leetcode] Longest Substring Without Repeating Cha

摘要：哈希表是最自然的想法。在遍歷字符串時，我們先根據哈希表找出該字符上次出現的位置，如果大于等于子字符串首，便更新子字符串首。結束后，將該字符新的位置放入哈希表中。 Longest Substring Without Repeating Characters 最新更新解法：https://yanjia.me/zh/2018/12/... Given a string, find the ...

FleyX 2019-08-14 12:18 評論0 收藏0