無重復字符的最長子串-有解無憂

題目：

　　給定一個字串，請你找出其中不含有重復字符的最長子串的長度，

題解：

　　看到判斷是否重復，我們首先應該想到Set，因為Set存盤的是無重復的、無排序的元素，假如看到統計元素的個數，首先應該想到Map，只有使用了對的資料結構，才能使得我們的代碼的運行效率更高，時間復雜度更低，在空間和時間的取舍上，我們一貫的思維是空間換時間，畢竟韶光易逝不復返，但機器硬體我們是可以堆砌出來的，

　　在計算器網路中，滑動視窗機制相信我們都有所了解，它是TCP/IP的可靠傳輸的保證機制，子串的含義是字符之間的位置要是連續的、有序的（相對位置不變），這恰恰符合滑動視窗的思想，所以，接下里我們就來是滑動視窗演算法來解決此題，

　　1.使用Set來判斷字符是否有重復

　　2.假如字符有重復，那么就將視窗的左邊界移到到重復字符的下一個位置，這樣就能保證視窗中的字符構成的是無重復字符的、有序的子串，下面上代碼：

Java版本

public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0) return 0;
        
        int maxLen = 0;
        for(int i=0;i<s.length();i++){
            //滑動視窗 Set
            Set<Character> set = new HashSet<Character>();//判斷是否有重復
            set.add(s.charAt(i));
            for(int j=i+1;j<s.length();j++){
                char c= s.charAt(j);
                if(!set.contains(c)) set.add(c);
                else{//有重復的元素
                    maxLen = Math.max(maxLen,set.size());
                    //洗掉重復的元素，即將視窗的左邊界移到到重復字符的下一個位置
                    while(set.contains(c)){
                        set.remove(s.charAt(i++));
                    }
                    set.add(c);
                }
            }
            maxLen = Math.max(maxLen,set.size());
        }
        return maxLen;

    }

JS版本

var lengthOfLongestSubstring = function(s){
    if(!s || s.length ==0){
        return 0;
    }
    var j =0,i = 0,maxLen = 0;
    var set = new Set();
    for(i;i < s.length;i ++){
        if(!set.has(s[i])){
            set.add(s[i]);
            maxLen = Math.max(maxLen,set.size);
        }else{//將視窗的左邊界移到到重復字符的下一個位置
            while(set.has(s[i])){
                set.delete(s[j]);
                j++;
            }
            set.add(s[i]);
        }
    }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/261291.html

標籤：其他

上一篇：CUDA 執行緒ID 計算方式；NVIDIA GPGPU；

下一篇：編譯器實作之旅——第四章實作詞法分析器