sliding window
Topic introduction
76. LeetCode (LeetCode CN. Com)
This topic says that we should at least ask for a substring. If we can't find a substring,
How to find the shortest one,
Let's assume that we have a table to record how many times each letter appears and how many times one appears, and we store it in an array,
Then we cycle our s string. As long as the s string appears, we will reduce the number of corresponding elements in the table we just remember by one. But here we need to pay attention to one problem, that is, not every deletion will delete the total number. In fact, it is not. Sometimes what you give may not be what others want, If you pay back what others don't want, you can force it, but it won't reduce your debt, but the reduced amount can still be reduced, because this amount will be useful, that is, once we find a satisfactory position, we can reduce it, but there is a premise for this reduction, that is, what you have exceeded is our negative number, Explain how many in your s string, and it doesn't affect your reduction at this time. But if you have 0, you can't reduce it. If you reduce it, it will lead to debt, which is not satisfied. Therefore, my reduction also depends on the situation
public String minWindow(String s, String t) {
if(s.length()<t.length()){
return "";
}
char[] chars = s.toCharArray();//This step is to convert the string to an array
char[] chart=t.toCharArray();
int[]arr=new int[266];//Our data is stored here, which means that each data appears several times
for(char x:chart){
arr[x]++;//For data statistics, how many times does each character appear
}
int all=t.length();//This is the total length. Our data is put in it
int L=0;
int R=0;
int ansL=0;
int ansR=0;//Determine the left and right borders to facilitate our final statistics
int minLength=Integer.MAX_VALUE;
while(R!=s.length()){
//Pay the bill when you come in
arr[chars[R]]--;
if(arr[chars[R]]>=0){//That means we haven't paid our bills yet
all--;
}
if(all==0){
while(arr[chars[L]]<0){
arr[chars[L++]]++;//I'm in debt again
}
if(minLength>R-L+1){
minLength=R-L+1;
ansL=L;
ansR=R;
}
arr[chars[L++]]++;
all++;//Total debt plus 1
}
R++;
}
return minLength==Integer.MAX_VALUE?"":s.substring(ansL,ansR+1);
}
The problem of the smallest string
Given A positive integer array A, if the number of different integers in A subarray of A is exactly K, the continuous and not necessarily different subarray of A is called A good subarray.
(for example, there are three different integers in [1,2,3,1,2]: 1, 2, and 3.)
Returns the number of good subarrays in A.
//This is our case
Input: A = [1,2,1,2,3], K = 2
Output: 7
Explanation: a subarray consisting of exactly two different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]
The key to this problem is that we should think of subtracting k-1 non repeated sub arrays with the help of the maximum K non repeated sub arrays, which is exactly equal to K
1. First, create a map to help us store the number and type of data in our array. How many times does it appear
2. Processing. What should we do when we exceed the category? When we exceed the category, we need to move the left window. If we must remove one of the left window, we can continue our ans processing, that is, we can enter our addition processing, and the data in the window must not exceed the specified value.
public int subarraysWithKDistinct(int[] nums, int k) {
return numsMostK(nums, k)-numsMostK(nums, k-1);//By subtracting the maximum k-1 non repeating sub arrays from the maximum K non repeating sub arrays, we are exactly equal to
}
public static int numsMostK(int[]arr,int k){
int n=arr.length;
int ans=0;
int []map=new int[n+1];//That is, the size of our array should at least be greater than
for(int left=0,right=0,kinds=0;right<arr.length;right++){
if(map[arr[right]]++==0){//In any case, this + + has to be nb
kinds++;
}
while(kinds>k){//When our species are super
map[arr[left]]--;//Our subtraction involves the operation of returning to 0. As long as we make a subtraction, we have to make a judgment
if(map[arr[left]]==0){//
kinds--;
}
left++;//Make sure we have those integers in our window! [insert picture description here]( https://img-blog.csdnimg.cn/b5b08c6b81404ba8ae8d85252f79788b.gif#pic_center)
}
//Kings < = k is here
ans+=right-left;//This is a dynamic programming. We can find that these subarrays will be added every time we move
}
return ans;//This will do
}
Continue to refuel tomorrow