摘要：同時利用來存儲當前結果值所在的起始下標。然而，一旦出現重復值后，例如輸入的為，則無法判斷當前重復值是否應當在結果集中。如果中的元素都被清空，則代表該子數組符合要求，即將起始下標添加進入結果集。利用左右指針來限定最小子數組的范圍，即窗口大小。

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).

輸入一個字符串s和一個字符串數組words，其中words中的每個word的長度都相等。在字符串中找到所有子字符串的起始下標，只要該子字符串滿足words中所有單詞的連接結果（順序無關）

在思路一中，我利用HashMap來存儲對應的word所在的最近的下標。同時利用start來存儲當前結果值所在的起始下標。這樣做是為了滿足只對字符串進行一次遍歷就可以得出所有的結果值。但是當輸入的words中存在重復值時，該方法就會出現問題。因為該方法利用當前word的下標和start進行比較之后，判斷是否要移動start的位置。如果word的下標大于start說明該值重復，則將start移到word下標的下一位。然而，一旦出現重復值后，例如輸入的words為["good","bad","good"]，則無法判斷當前重復值是否應當在結果集中。
代碼如下：

    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中會有重復值，就想到利用map中來存儲word和其數量來判斷當前下標下的子數組中是否包含了map中所有的元素。如果map中的元素都被清空，則代表該子數組符合要求，即將起始下標添加進入結果集。
該方法有一個缺陷在于，每一次移動起始下標，都要重新初始化一個map的副本。而在很多情況下，該副本可能根本就沒有發生改變。這樣的內存利用率太低了，影響程序的效率。

    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
該思路是我借鑒了一個solution中的回答。minimum-window-substring是指，在尋找到所有元素都被包含進去的最小子數組中，判斷是否滿足目標要求。利用左右指針來限定最小子數組的范圍，即窗口大小。同時左右指針每次都按照固定長度右移，以便尋找到下一個最小子數組。具體情況請參考代碼中的注釋。
    public List findSubstring3(String s, String[] words) {
        //N為字符串長度
        int N = s.length();
        //結果集,長度必定不超過字符串長度
        List indexes = new ArrayList(s.length());
        if (words.length == 0) {
            return indexes;
        }
        //M為單個單詞的長度
        int M = words[0].length();
        //如果所有單詞連接之后的長度超過字符串長度，則返回空結果集
        if (N < M * words.length) {
            return indexes;
        }
        //last 字符串中最后一個可以作為單詞起始點的下標
        int last = N - M + 1;
        
        //map存儲word和其在table[0]中對應的下標
        Map mapping = new HashMap(words.length);
        //table[0]存儲每個word出現的真實次數，table[1]存儲每個word目前為止出現的統計次數
        int [][] table = new int[2][words.length];
        //failures存儲words中不重復值的總數，例如["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，判斷字符串當前下標后是否存在words中的單詞，如果存在，則填入table中的下標，不存在則為-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
            //保證右節點不超出邊界
            while (right < last) {
                //保證左右節點之間的子字符串能夠包含所有的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;
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~