Shortest Supersequence：在一个大数组big中找到一个子数组，该子数组包含所有在小数组small中的元素，顺序任意。

暴力查找法大概是这样的思路：对于big的每一个起始位置，遍历small中的每一个元素，找到其在big中距离起始位置最近的位置，当small中所有元素在后面都能找到时，更新最短区间。时间复杂度为O(b ^ 2 * s)，b和s分别表示两个数组的大小。十万的数据量，不超时就怪了。

可以通过一次预先的计算，优化掉每一次的遍历，也就是优化掉查找每一位置后距离该位置最近的元素的下标的过程，这样时间复杂度就变成了O(bs)。预计算可以通过反向扫描big数组实现。

运行结果为40 / 42，还是因为数据量太大而超时了。

class Solution {
private:vector<vector<int>> Table;void buildTable(const vector<int> &big, const vector<int> &small){Table.assign(big.size(), vector<int>(small.size(), big.size()));for(size_t i = 0; i < small.size(); i++){size_t closestIdx = big.size();for(size_t j = big.size(); j > 0; j--){if(big[j - 1] == small[i]) closestIdx = j - 1;Table[j - 1][i] = closestIdx;}}}vector<int> findShortestRange(){int left = 0, right = Table.size();for(size_t i = 0; i < Table.size(); i++){size_t start = i;size_t max = i;for(size_t j = 0; j < Table[0].size(); j++){if(max < Table[i][j]) max = Table[i][j];}if(max != Table.size() && max - start < right - left){left = start;right = max;}}if(right == Table.size()) return {};return { left, right };}
public:vector<int> shortestSeq(vector<int>& big, vector<int>& small) {buildTable(big, small);return findShortestRange();}
};

从上面的代码来看，buildTable()和findShortestRange()明显重复了，后者查找每一行的最大值，这完全可以在建表的时候完成，只需要增加一下判断逻辑即可：如果Table[j - 1]为初始值，或者小于closestIdx，就对其进行更新，当然因为还是O(bs)的复杂度，所以通过率还是40 / 42。

class Solution {
private:vector<int> BuildAndFind(const vector<int> &big, const vector<int> &small){vector<int> Table(big.size(), -1);const int MAX = static_cast<int>(big.size());for(size_t i = 0; i < small.size(); i++){size_t closestIdx = big.size();for(size_t j = big.size(); j > 0; j--){if(big[j - 1] == small[i]) closestIdx = j - 1;if(Table[j - 1] == -1 || (Table[j - 1] < closestIdx)){Table[j - 1] = closestIdx;}}}int left = 0, right = MAX;for(int i = 0; i < Table.size(); i++){if(Table[i] != MAX && Table[i] - i < right - left){left = i;right = Table[i];}}if(right != MAX) return { left, right };else return {};}
public:vector<int> shortestSeq(vector<int>& big, vector<int>& small) {return BuildAndFind(big, small);}
};

如果已经提前计算得到了small中每个元素在big中的所有位置，则按照类似归并排序的方式，可以计算得到最小的区间：所有队列中的最小和最大队头元素就是第一个区间，然后将最小的队头移除，得到第二个区间，重复这个过程，找到所有的区间，这个过程中，通过堆heap和变量Max维护这个区间。队列中元素数量的上限为b，每个元素在放入堆中时需要log(s)次比较调整，所以时间复杂度为O(blogs)。

class Solution {
private:vector<list<int>> Queues;void buildQueue(const vector<int> &big, const vector<int> &small){unordered_map<int, list<int>> Locations;for(int s : small){Locations.insert(make_pair(s, list<int>()));}for(int i = 0; i < static_cast<int>(big.size()); i++){auto iter = Locations.find(big[i]);if(iter != Locations.end()) iter->second.push_back(i);}for(auto iter = Locations.begin(); iter != Locations.end(); iter++){Queues.push_back(iter->second);}}struct HeapNode{int index;size_t QueueNumber;HeapNode(const int idx, const size_t qn) : index(idx), QueueNumber(qn){}bool operator>(const HeapNode &hn) const{return index > hn.index;}};vector<int> findClosestRange(){priority_queue<HeapNode, vector<HeapNode>, greater<HeapNode>> heap;HeapNode Max(INT_MIN, 0);for(size_t i = 0; i < Queues.size(); i++){if(Queues[i].empty()) return {};HeapNode tmp(Queues[i].front(), i);heap.push(tmp);Queues[i].pop_front();if(tmp > Max) Max = tmp;}int left = heap.top().index, right = Max.index;while(1){HeapNode top = heap.top();heap.pop();size_t qn = top.QueueNumber;if(Queues[qn].empty()) break;HeapNode tmp(Queues[qn].front(), qn);heap.push(tmp);Queues[qn].pop_front();if(tmp > Max) Max = tmp;if(Max.index - heap.top().index < right - left){left = heap.top().index;right = Max.index;}}return { left, right };}
public:vector<int> shortestSeq(vector<int>& big, vector<int>& small) {buildQueue(big, small);return findClosestRange();}
};

从上面描述的过程来看，这就是一个滑动窗口的做法：我们可以先找到第一个区间，然后缩短左边界直到出现无效区间，再扩充右边界直到出现下一个区间，反复重复这个过程直到找到最小区间。这个过程中，要通过一个映射SmallCount来记录有效区间中的small中每个元素的数量。

class Solution {
public:vector<int> shortestSeq(vector<int>& big, vector<int>& small) {map<int, size_t> SmallCount;for(int s : small){SmallCount[s] = 0;}size_t count = SmallCount.size(), left = 0, right = 0;for(right = 0; right < big.size(); right++){auto iter = SmallCount.find(big[right]);if(iter != SmallCount.end()){iter->second++;if(iter->second == 1) count--;if(count == 0) break;}}if(count != 0) return {};size_t i = left, j = right;while(j < big.size()){for(; i < big.size(); i++){auto iter = SmallCount.find(big[i]);if(iter != SmallCount.end()){iter->second--;if(iter->second == 0) break;}}if(j - i < right - left){left = i;right = j;}for(i = i + 1, j = j + 1; j < big.size(); j++){auto iter = SmallCount.find(big[j]);if(iter != SmallCount.end()){iter->second++;if(iter->second == 1) break;}}if(j - i < right - left){left = i;right = j;}}return { static_cast<int>(left), static_cast<int>(right) };}
};