子数组查找

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
const int max_size=100000;
int min_array(vector<int>& nums,unordered_map<int,int>& sets,int m)
{
	int min_length = max_size+1;
	int i=0, j=0;//初始窗口
	int count = 0;//窗口中已经包含的数字集中元素的个数
	
	while(j<nums.size())//窗口右边往右扩张
	{
		if (sets.find(nums[j])!=sets.end())//如果该数在数字集中
		{
			if(sets[nums[j]]==0)//且该数出现次数为0
				count++;//则包含元素个数++
			sets[nums[j]]++;//该元素出现次数++
            while (count==m)//当包含元素个数=数字集个数时，
            {//说明已经包含了数字集所有元素,开始移动i，缩小窗口
                if (sets.find(nums[i])!=sets.end())//当遇到数字集中的元素时
                {
                    if (j - i + 1 < min_length)//更新最小长度
                        min_length = j - i + 1;
                    if (sets[nums[i]] > 0)//该元素出现次数--
                        sets[nums[i]]--;
                    if(sets[nums[i]]==0)//若某元素出现次数=0；表面已经到达有效窗口的极限位置
                    {
                        count--;//包含元素个数--，表明还差了一个元素。下次再遇到该元素时，又是有效窗口
                        i++;
                        break;
                    }
                }
                i++;
            }
		}
		j++;
	}

	if (min_length == max_size + 1)
		return 0;
	else
		return min_length;
}

int main()
{
	int T;
	cin >> T;
	int n,m;
	int num;
	for (int i = 0; i < T; i++)
	{
        vector<int> nums;
		unordered_map<int, int> sets;//数字集
		cin >> n;
		for (int j = 0; j < n; j++)
		{
			cin >> num;
			nums.push_back(num);
		}
		cin >> m;
		for (int j = 0; j < m; j++)
		{
			cin >> num;
			sets[num] = 0;//初始化数字集中每个数字的出现次数
		}

		cout << min_array(nums,sets,m) << endl;
	}
	return 0;
}

给个python滑动窗口的代码

from collections import defaultdict
class Solution():
    def f(self,n,m,src_arr,tgt_arr):
        needed=defaultdict(int)
        window=defaultdict(int)

        for item in tgt_arr:
            needed[item]+=1
        needed_len=len(needed)
        cur_len=0
        min_len=100000
        left,right=0,0
        while right<n:
            if src_arr[right] in needed:
                pre=window[src_arr[right]]
                window[src_arr[right]]+=1
                if pre<needed[src_arr[right]] and window[src_arr[right]]>=needed[src_arr[right]]:
                    cur_len+=1 # 已经满足一个了
            while cur_len==needed_len:# 所有的key满足了
                min_len=min(min_len,right-left+1)
                left_item=src_arr[left]
                if left_item in needed:
                    window[src_arr[left]]-=1
                    if window[src_arr[left]]<needed[src_arr[left]]:
                        cur_len-=1
                left+=1
            right+=1 # 向右移动一格
        return min_len if min_len!=100000 else 0
sol=Solution()
n=int(input().strip())
for i in range(n):
    n=int(input().strip())
    src=[int(item) for item in input().strip().split()]
    m=int(input().strip())
    tgt=[int(item) for item in input().strip().split()]
    # print(n,src,m,tgt)
    res=sol.f(n,m,src,tgt)
    print(res)

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <cctype>
#include <ctime>
#include <map>
using namespace std;
const int maxn=1e5+5;
int a[maxn],b[maxn],c[maxn],d[maxn];
bool vis[maxn];
int en,m,n;
int getid(int x){
    return lower_bound(b+1,b+en+1,x)-b;
}
bool check(int len){
    int cnt=0;
    for(int i=1;i<=en;i++) d[i]=0;
    for(int i=1;i<=len;i++){
        if(c[a[i]]==1){
            if(d[a[i]]==0) cnt++;            
            d[a[i]]++;
        } 
    }
    if(cnt==m) return true;
    for(int i=len+1;i<=n;i++){
        int p=i-len;
        if(c[a[p]]){
            if(d[a[p]]==1) cnt--;
            d[a[p]]--;
        }
        if(c[a[i]]==1){
            if(d[a[i]]==0) cnt++;            
            d[a[i]]++;
        } 
        if(cnt==m) return true;
    }
    return false;
}

int main(){
    int T;
    ios::sync_with_stdio(false);
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i],c[i]=0;
        sort(b+1,b+n+1);
        en=unique(b+1,b+n+1)-b-1;
        for(int i=1;i<=n;i++) a[i]=getid(a[i]);
        cin>>m;
        bool flag=true;
        for(int i=1;i<=m;i++) {
            int k;
            cin>>k;
            int x=getid(k);
            if(b[x]!=k) flag=false;
            else c[x]=1;
        }
        if(flag){
            int l=m,r=n;
            while(l<=r){
                int mid=(l+r)/2;
                if(check(mid)) r=mid-1;
                else l=mid+1;
            }
            printf("%d\n",l);
        }else{
            puts("0"); 
        }


    }

    return 0;
}

import java.util.Scanner;

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int count=in.nextInt();
            for(int i=0;i<count;i++){
                int src=in.nextInt();
                int[] nums=new int[src];
                for(int j=0;j<src;j++){
                    nums[j]=in.nextInt();
                }
                int target=in.nextInt();
                Map<Integer,List<Integer>> record=new HashMap<>();
                Set<Integer> set=new HashSet<>();
                PriorityQueue<int[]> queue=new PriorityQueue<>((a,b)->a[1]-b[1]);//数组位置升序
                for(int j=0;j<target;j++){
                    record.put(in.nextInt(),new ArrayList<Integer>());
                }
                int right=0;
                //记录目标值的坐标，从小到大
                for(int j=0;j<src;j++){
                    if(record.containsKey(nums[j])){
                        record.get(nums[j]).add(j);
                        int position=record.get(nums[j]).size()-1;
                        if(set.add(nums[j])){
                            right=Math.max(right,j);
                            queue.add(new int[]{nums[j],j,position});

                        }
                    }
                }
                if(queue.size()!=target){
                    System.out.println(0);
                }else{
                    int ans=right-queue.peek()[1]+1;//记录最小子数组长度

                    while(true){
                        int[] cur=queue.peek();
                        List<Integer> curList=record.get(cur[0]);
                        if(cur[2]<curList.size()-1){
                            //说明还存在变化的可能性
                            int future=curList.get(cur[2]+1);
                            if(future>right){
                                right=future;
                            }
                            queue.poll();
                            queue.add(new int[]{cur[0],future,cur[2]+1});
                            ans=Math.min(ans,right-queue.peek()[1]+1);
                        }else{
                            break;
                        }
                    }
                    System.out.println(ans);
                }
            }
        }
    }
}

#维护滑动窗，超时，只能60%
from collections import defaultdict
class Solution:
    #判断窗内是否包含所有要求的数字
    def window_contain_target(self, w1, w2):
        res = True
        for k,v in w2.items():
            if k not in w1.keys()&nbs***bsp;w1[k] < v:
                res = False
                break
        return res
    #维护滑动窗
    def minWindow(self, s: str, t: str) -> str:
        left = 0
        target = defaultdict(int)
        window = defaultdict(int)
        window_len = float("inf")
        res = ""
        for char in t:
            target[char] += 1
        #右扩滑动窗
        for right in range(0, len(s)):
            window[s[right]] += 1
            #左缩滑动窗
            while self.window_contain_target(window, target):
                if window_len > (right-left+1):
                    window_len = right-left+1
                    res = s[left:right+1]
                window[s[left]] -= 1
                if window[s[left]] == 0:
                    del window[s[left]]
                left += 1
        return res

T = int(input())
for i in range(T):
    n = int(input())
    nums = [int(i) for i in input().split()]
    m = int(input())
    query = [int(i) for i in input().split()]
    solution = Solution()
    res = solution.minWindow(nums, query)
    print(len(res))

#include<bits/stdc++.h>
using namespace std;
int main(){
    int T; cin >> T;
    while(T--) {
        int N; cin >> N; 
        int a[N]; for(int i=0; i<N; ++i) cin >> a[i];
        
        set<int> s;
        int M; cin >> M;
        for(int i=0, val; i<M; ++i) cin >> val, s.insert(val);
        
        priority_queue<int, vector<int>, greater<int>> pq;
        map<int, int> m;
        int res = INT_MAX;
        for(int i=0, cnt = 0; i<N; ++i) {
            if(s.count( a[i] )) {
                pq.push(i);
                m[a[i]]++;
                cnt += m[a[i]]==1;
            }
            if(cnt >= M) {
                while(m[a[pq.top()]] > 1) m[a[pq.top()]]--, pq.pop();
                res = min(res, i - pq.top() + 1);
            }
        }
        cout << (res == INT_MAX ? 0 : res) << endl;
    }
    return 0;
}

import sys

def min_len(nums, subnums, lengths):

    sub_dict = {}
    for i in range(len(subnums)):
        sub_dict[subnums[i]] = -1

    min_length = len(nums) + 1
    find_num = 0
    pos = 0
    while pos < len(nums):
        if sub_dict.get(nums[pos], -2) != -2:
            if sub_dict[nums[pos]] == -1:
                find_num += 1
            sub_dict[nums[pos]] = pos

        if find_num == len(subnums):
            max_pos = max(sub_dict.values())
            min_pos = min(sub_dict.values())
            length = max_pos - min_pos + 1
            if length < min_length:
                min_length = length
            sub_dict[nums[min_pos]] = -1
            find_num -= 1
        pos += 1

    min_length = min_length if min_length != len(nums) + 1 else 0

    lengths.append(min_length)


total = int(input())
lengths = []
for i in range(total):

    sys.stdin.readline()
    nums = sys.stdin.readline().strip().split()
    nums = list(map(int, nums))
    sys.stdin.readline()
    subnums = sys.stdin.readline().strip().split()
    subnums = list(map(int, subnums))
    min_len(nums, subnums, lengths)
for length in lengths:
    print(length)

## 60%，超时了
def solve(nums, child_nums):
    num_dict = {}
    window = {}
    length = float("inf")
    left, right = 0, 0
    for num in child_nums:
        num_dict[num] = num_dict.get(num, 0) + 1
    target = len(num_dict.keys())
    while right < len(nums):

        if nums[right] in child_nums:
            window[nums[right]] = window.get(nums[right], 0) + 1
            if window[nums[right]] == num_dict[nums[right]]:
                target -= 1
        
        while target == 0:
            length = min(length, right - left + 1)
            if nums[left] in child_nums:
                window[nums[left]] -= 1
            if window[nums[left]] < num_dict[nums[right]]:
                target += 1
            left += 1
        right += 1
    return length if length != float("inf") else 0


N = int(input())
for _ in range(N):
    ## get data
    lens = int(input())
    nums = list(map(int, input().strip().split()))
    short_lens = int(input())
    child_nums = list(map(int, input().strip().split()))
    print(solve(nums, child_nums))

思路

• 使用滑动窗口来匹配子串，分别用start和end两个变量记录位置，然后通过字典记录需要的字符串的个数，key为需要的字符，val为个数，额外使用一个计数变量satisfied记录满足匹配条件的字符个数，当其值等于要查找的子串长度时说明找到了满足条件的子串。
  • 开始时一直移动end并检查是否是需要的字符并计数，当数量满足时开始移动左边界start从而缩小范围，直到end遍历到数组的最后。

def find_min_length(M,N,m_nums,need_dict):
    min_length = 100000
    satisfied = 0
    #存储目标字符串中需要的字符的个数
    src_dict = {}
    start,end = 0,0
    #滑动窗口最后的位置，end到达数组尾
    while end < M:
        # end向右滑动知道找到包含need所有字符的窗口
        if m_nums[end] in need_dict.keys():
            src_dict[m_nums[end]] = src_dict.get(m_nums[end],0)+1
        if src_dict[m_nums[end]] == need_dict[m_nums[end]]:
            satisfied += 1
        # 找到满足条件的子串后求其长度，并移动左边的窗口坐标
        while satisfied == N:
            min_length = min(min_length,end-start+1)
            if m_nums[start] in need_dict.keys():
                src_dict[m_nums[start]] -= 1
                # 重新判断新的窗口是否符合条件，不符合条件的话需要移动右窗口
                if src_dict[m_nums[start]] < need_dict[m_nums[start]]:
                    satisfied -= 1
            start += 1
        end += 1
    return min_length if min_length != 100000 else 0

def main():
    T = int(input())
    for i in range(T):
        M = int(input())
        m_nums = list(map(int,input().split()))
        N = int(input())
        n_nums = list(map(int,input().split()))

        need_dict = {}
        for i in range(N):
            need_dict[n_nums[i]] = need_dict.get(n_nums[i],0)+1
        min_length = find_min_length(M,N,m_nums, need_dict)
        print(min_length)
main()