摘要：同時(shí)利用來存儲(chǔ)當(dāng)前結(jié)果值所在的起始下標(biāo)。然而，一旦出現(xiàn)重復(fù)值后，例如輸入的為，則無法判斷當(dāng)前重復(fù)值是否應(yīng)當(dāng)在結(jié)果集中。如果中的元素都被清空，則代表該子數(shù)組符合要求，即將起始下標(biāo)添加進(jìn)入結(jié)果集。利用左右指針來限定最小子數(shù)組的范圍，即窗口大小。

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

輸入一個(gè)字符串s和一個(gè)字符串?dāng)?shù)組words，其中words中的每個(gè)word的長度都相等。在字符串中找到所有子字符串的起始下標(biāo)，只要該子字符串滿足words中所有單詞的連接結(jié)果（順序無關(guān)）

在思路一中，我利用HashMap來存儲(chǔ)對(duì)應(yīng)的word所在的最近的下標(biāo)。同時(shí)利用start來存儲(chǔ)當(dāng)前結(jié)果值所在的起始下標(biāo)。這樣做是為了滿足只對(duì)字符串進(jìn)行一次遍歷就可以得出所有的結(jié)果值。但是當(dāng)輸入的words中存在重復(fù)值時(shí)，該方法就會(huì)出現(xiàn)問題。因?yàn)樵摲椒ɡ卯?dāng)前word的下標(biāo)和start進(jìn)行比較之后，判斷是否要移動(dòng)start的位置。如果word的下標(biāo)大于start說明該值重復(fù)，則將start移到word下標(biāo)的下一位。然而，一旦出現(xiàn)重復(fù)值后，例如輸入的words為["good","bad","good"]，則無法判斷當(dāng)前重復(fù)值是否應(yīng)當(dāng)在結(jié)果集中。
代碼如下：

    public List findSubstring(String s, String[] words) {
        List result = new ArrayList();
        if(words.length == 0){
            return result;
        }
        int wordLength = words[0].length();
        int allWordsLength = words.length;
        Map wordMap = new HashMap();
        
        for(int j = 0 ; j=start){
                    start = key + wordLength;
                //長度等于所有長度
                }else if(i-start == wordLength*(allWordsLength-1)){
                    result.add(start);
                    start+=wordLength;
                }    
                wordMap.replace(current, i);
                i+=wordLength;
                continue;
            }
            i++;
            start = i;
        }
        return result;
    }

既然words中會(huì)有重復(fù)值，就想到利用map中來存儲(chǔ)word和其數(shù)量來判斷當(dāng)前下標(biāo)下的子數(shù)組中是否包含了map中所有的元素。如果map中的元素都被清空，則代表該子數(shù)組符合要求，即將起始下標(biāo)添加進(jìn)入結(jié)果集。
該方法有一個(gè)缺陷在于，每一次移動(dòng)起始下標(biāo)，都要重新初始化一個(gè)map的副本。而在很多情況下，該副本可能根本就沒有發(fā)生改變。這樣的內(nèi)存利用率太低了，影響程序的效率。

    public List findSubstring2(String s, String[] words) {
        List result = new ArrayList();
        if(words.length == 0){
            return result;
        }
        int wordLength = words[0].length();
        int allWordsLength = words.length;
        
        
        Map wordMap = new HashMap();
        for(int j = 0 ; j copy = new HashMap(wordMap);
            for(int i=start ; i
思路三 ：minimum-window-substring
該思路是我借鑒了一個(gè)solution中的回答。minimum-window-substring是指，在尋找到所有元素都被包含進(jìn)去的最小子數(shù)組中，判斷是否滿足目標(biāo)要求。利用左右指針來限定最小子數(shù)組的范圍，即窗口大小。同時(shí)左右指針每次都按照固定長度右移，以便尋找到下一個(gè)最小子數(shù)組。具體情況請(qǐng)參考代碼中的注釋。
    public List findSubstring3(String s, String[] words) {
        //N為字符串長度
        int N = s.length();
        //結(jié)果集,長度必定不超過字符串長度
        List indexes = new ArrayList(s.length());
        if (words.length == 0) {
            return indexes;
        }
        //M為單個(gè)單詞的長度
        int M = words[0].length();
        //如果所有單詞連接之后的長度超過字符串長度，則返回空結(jié)果集
        if (N < M * words.length) {
            return indexes;
        }
        //last 字符串中最后一個(gè)可以作為單詞起始點(diǎn)的下標(biāo)
        int last = N - M + 1;
        
        //map存儲(chǔ)word和其在table[0]中對(duì)應(yīng)的下標(biāo)
        Map mapping = new HashMap(words.length);
        //table[0]存儲(chǔ)每個(gè)word出現(xiàn)的真實(shí)次數(shù)，table[1]存儲(chǔ)每個(gè)word目前為止出現(xiàn)的統(tǒng)計(jì)次數(shù)
        int [][] table = new int[2][words.length];
        //failures存儲(chǔ)words中不重復(fù)值的總數(shù)，例如["good","bad","good","bad"]，failures=2
        int failures = 0, index = 0;
        for (int i = 0; i < words.length; ++i) {
            Integer mapped = mapping.get(words[i]);
            if (mapped == null) {
                ++failures;
                mapping.put(words[i], index);
                mapped = index++;
            }
            ++table[0][mapped];
        }
        
        //遍歷字符串s，判斷字符串當(dāng)前下標(biāo)后是否存在words中的單詞，如果存在，則填入table中的下標(biāo)，不存在則為-1
        int [] smapping = new int[last];
        for (int i = 0; i < last; ++i) {
            String section = s.substring(i, i + M);
            Integer mapped = mapping.get(section);
            if (mapped == null) {
                smapping[i] = -1;
            } else {
                smapping[i] = mapped;
            }
        }
        
        //fix the number of linear scans
        for (int i = 0; i < M; ++i) {
            //reset scan variables
            int currentFailures = failures; //number of current mismatches
            int left = i, right = i;
            Arrays.fill(table[1], 0);
            //here, simple solve the minimum-window-substring problem
            //保證右節(jié)點(diǎn)不超出邊界
            while (right < last) {
                //保證左右節(jié)點(diǎn)之間的子字符串能夠包含所有的word值
                while (currentFailures > 0 && right < last) {
                    int target = smapping[right];
                    if (target != -1 && ++table[1][target] == table[0][target]) {
                        --currentFailures;
                    }
                    right += M;
                }
                while (currentFailures == 0 && left < right) {
                    int target = smapping[left];
                    if (target != -1 && --table[1][target] == table[0][target] - 1) {
                        int length = right - left;
                        //instead of checking every window, we know exactly the length we want
                        if ((length / M) ==  words.length) {
                            indexes.add(left);
                        }
                        ++currentFailures;
                    }
                    left += M;
                }
            }
            
        }
        return indexes;
    }

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~