leetcode 30 线性时间复杂度？

求问 为啥 leetcode 30 Substring with Concatenation of All Words 会是线性的时间复杂度呢？   谢谢大家！ 贴一下九章的解法：

class Solution {public:    vector<int> findSubstring(string s, vector<string>& words) {        vector<int> result;        if (words.size() == 0) {            return result;        }                unordered_map<string, int> hash;        for (int i = 0; i < words.size(); i++) {            if (hash.find(words[i]) == hash.end()) {                hash[words[i]] = 1;            } else {                hash[words[i]]++;            }        }                int wSize = words[0].length();        for (int start = 0; start < wSize; start++) {            int wCount = 0;            unordered_map<string, int> slidingWindow;            for (int i = start; i + wSize <= s.length(); i+=wSize) {                string word = s.substr(i, wSize);                if (hash.find(word) == hash.end()) {                    slidingWindow.clear();                    wCount = 0;                } else {                    wCount++;                    if (slidingWindow.find(word) == slidingWindow.end()) {                        slidingWindow[word] = 1;                    } else {                        slidingWindow[word]++;                    }                    while (hash[word] < slidingWindow[word]) {                        string removedWord = s.substr(i - (wCount-1) * wSize, wSize);                        slidingWindow[removedWord]--;                        wCount--;                    }                }                                if (wCount == words.size()) {                    result.push_back(i - (wCount - 1) * wSize);                }            }        }                return result;    }};

严格的线性需要自己写hash，做法可以这样。
枚举答案的左端点，那么右端点也就可以计算出，这样的复杂度是O(N)的。
对于左端点右端点中间的所有小区间计算hash，比较和输入的所有单词是不是一样，这个需要O(words*hash_word)的时间。
这样总的复杂度是N*words*hash_word的复杂度。
严格意义上来说你hash一个字符串需要的时间和长度肯定是相关的，要优化的话可以自己对于s写手动的hash这样你hashmap只要存int就可以了。
words这个怎么优化就在于比如s长度为10，有2个长度为3的单词，那么你统计[0,2][3,5]的时候其实和[3,5][6,9]只差了头和尾2个不同的单词，常数统计一下，这样平均下来就是线性的了。
楼主给的代码不是线性的，一旦用上了substr或者hashmap.find(string)的话肯定不是严格的线性。
可以看看hash的code就知道了。
public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;
            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }