假设你有两个数组,一个长一个短,短的元素均不相同。 找到长数组中包含短数组所有的元素的最短子数组,其出现顺序无关紧要。
返回最短子数组的左端点和右端点,如有多个满足条件的子数组,返回左端点最小的一个。 若不存在,返回空数组。
示例 1:
输入:
big = [7,5,9,0,2,1,3,5,7,9,1,1,5,8,8,9,7]
small = [1,5,9]
输出: [7,10]
示例 2:
输入:
big = [1,2,3]
small = [4]
输出: []
提示:
big.length <= 100000
1 <= small.length <= 100000
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/shortest-supersequence-lcci 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
[i,j]
内存在于 set 内的元素的个数,当map计数为0是,将其删除map.size == set.size
,map的size不够,j++,够了,i++class Solution {
public:
vector<int> shortestSeq(vector<int>& big, vector<int>& small) {
if(big.size() < small.size())
return {};
int i=0, j=0, n = big.size(), k = small.size(), minLen = INT_MAX;
vector<int> ans(2,-1);
unordered_set<int> s;
unordered_map<int,int> m;
for(int c : small)
s.insert(c);
while(j < n)
{
while(j < n && m.size() < k)
{
if(s.count(big[j]))
m[big[j]]++;
j++;
}
while(i < j && m.size()==k)
{
if(j-i < minLen)
{
minLen = j-i;
ans[0] = i, ans[1] = j-1;
}
if(s.count(big[i]))
{
m[big[i]]--;
if(m[big[i]]==0)
m.erase(big[i]);
}
i++;
}
}
if(ans[0]==-1)
return {};
return ans;
}
};
372 ms 54.2 MB