前言
??????Leetcode算法系列：https://leetcode-cn.com/study-plan/algorithms/?progress=njjhkd2
??????简单总结一下滑动窗口相关的算法题：
一、无重复字符的最长子串
??????题目链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
??????题目描述：给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
思路 1：
??????用一个区间（窗口）来表示当前的无重复字符串，每当区间扩大1位的时候，需要判断当前扩充的元素和区间中哪位元素发生重复，不发生重复，区间长度加一；否则从重复元素的下一个元素作为区间的起始点，当前扩充的元素作为区间的结束点。依次遍历所有元素。
public int lengthOfLongestSubstring(String s) {
int i=0,end=s.length(),start=0;
int tmp=0,ans=0;
while(i<end){
int re=isNotDup(s,start,i);
if(re==-1)
tmp++;
else{
ans=tmp>ans?tmp:ans;
tmp=i-re+1;
start=re;
}
i++;
}
return ans>tmp?ans:tmp;
}
public int isNotDup(String a,int i,int j){
while(i<j){
if(a.charAt(i)==a.charAt(j))
return i+1;
i++;
}
return -1;
}
????? 时间复杂度为 O(n2)。
思路 2：
??????关于如何判断是否发生重复，以及设置区间的下一个起点，可以采用 Set 来做，如果发生重复的话：从上一个区间的起点依次将元素移出集合，直到不重复为止。参考算法如下：
public int lengthOfLongestSubstring(String s) {
Set<Character> container=new HashSet<>();
int i=0,end=s.length(),start=0;
int tmp=0,ans=0;
while(i<end){
if(!container.add(s.charAt(i))){
tmp=container.size();
ans=ans<tmp?tmp:ans;
for(int j=start;j<i;j++){
container.remove(s.charAt(j));
if(container.add(s.charAt(i))){
start=j+1;
break;
}
}
}
i++;
}
return ans>container.size()?ans:container.size();
}
????? 时间复杂度为 O(n2)。但是它的执行效率没有算法1 快。
二、字符串的排列
??????题目链接：https://leetcode-cn.com/problems/permutation-in-string/
??????题目描述：给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。
思路 1：
??????直观上，对 s1 求得全排列，然后分别对 s1 的所有排列验证是 s2 的子串。为了回顾 Kmp 和 全排列算法，参考代码如下：（但它的时间复杂度太高，在此不建议使用）
public boolean checkInclusion(String s1, String s2) {
if(s1.length()>s2.length())
return false;
ArrayList<String> re=new ArrayList<>();
arrange(re,s1.toCharArray(),0,s1.length()-1);
for(String tmp:re){
if(kmp(tmp,s2))
return true;
}
return false;
}
public static boolean kmp(String s1,String s2){
int len=s1.length();
int[] next=new int[len];
next[0]=-1;
int i=0,tmp;
while(++i<len){
tmp=next[i-1];
if(tmp==-1){
next[i]=0;
continue;
}
while(tmp!=-1&&s1.charAt(i-1)!=s1.charAt(tmp))
tmp=next[tmp];
next[i]=tmp+1;
}
int index1=0,index2=0;
while(index2<s2.length()){
while(s2.charAt(index2)!=s1.charAt(index1)){
index1=next[index1];
if(index1==-1)
break;
}
index2++;
index1++;
if(index1==len)
return true;
}
return false;
}
public void arrange(ArrayList<String> re,char[] a,int start,int end){
if(start==end)
re.add(new String(a));
else {
int index=start;
char tmp;
while(index<=end){
tmp=a[index];
a[index]=a[start];
a[start]=tmp;
arrange(re,a,start+1,end);
tmp=a[index];
a[index]=a[start];
a[start]=tmp;
index++;
}
}
}
思路 2：
??????以 s1 的第一个字符为基准，找到该字符在 s2 中每一次出现的位置 a0、a1、a2… ，且假设 s1 的长度为 len，那么在 a0 处从区间【a0-len+1，a0】直到【a0，a0+len-1】都有可能是 s1 的一个排列，其余的 a1，a2也是一样。对区间【a0-len+1，a0】直到【a0，a0+len-1】中的元素分别进行排序和排序后的 s1 比较判断是否相等。参考算法如下（其时间复杂度依然太高）：
public boolean checkInclusion(String s1, String s2) {
int len1=s1.length(),len2=s2.length();
if(len1>len2)
return false;
int start,end;
for(int j=0;j<len2;j++){
if(s1.charAt(0)==s2.charAt(j)){
start=j-len1+1;end=j;
if(start<0){
end=len1-1;
start=0;
}
for(;end<len2;start++,end++){
if(decide(s1,s2.substring(start,end+1)))
return true;
}
}
}
return false;
}
public boolean decide(String a,String b){
char[] aa=a.toCharArray();
char[] bb=b.toCharArray();
Arrays.sort(aa);
Arrays.sort(bb);
if(Arrays.equals(aa,bb))
return true;
return false;
}
思路 3：
??????在 2 的基础上，对区间【a0-len+1，a0】直到【a0，a0+len-1】中的元素和 s1 的比较采用统计字符个数的方法来判断是否相等。参考算法如下（其时间复杂度也比较高）：
public boolean checkInclusion(String s1, String s2) {
int len1=s1.length(),len2=s2.length();
if(len1>len2)
return false;
int start,end;
int[] count1=new int[26];
int[] count2=new int[26];
for(int j=0;j<len2;j++){
if(s1.charAt(0)==s2.charAt(j)){
start=j-len1+1;end=j;
if(start<0){
end=len1-1;
start=0;
}
for(;end<len2;start++,end++){
Arrays.fill(count1,0);
Arrays.fill(count2,0);
if(decide(s1,s2.substring(start,end+1),count1,count2))
return true;
}
}
}
return false;
}
public boolean decide(String a,String b,int[] count1,int[] count2){
for(int i=0;i<a.length();i++){
count1[a.charAt(i)-'a']++;
count2[b.charAt(i)-'a']++;
}
if(Arrays.equals(count1,count2))
return true;
return false;
}
思路 3 plus：
??????首先没必要每次都初始化数组 count1，它只需要初始化一次即可，其次对于 count2 没必要进行整体上的改变，每次只需要增加新元素的个数，减少旧元素的个数。参考算法如下：
public boolean checkInclusion(String s1, String s2) {
int len1=s1.length(),len2=s2.length();
if(len1>len2)
return false;
int start,end;
int[] count1=new int[26];
for(int i=0;i<len1;i++)
count1[s1.charAt(i)-'a']++;
int[] count2=new int[26];
for(int j=0;j<len2;j++){
if(s1.charAt(0)==s2.charAt(j)){
start=j-len1+1;end=j;
if(start<0){
end=len1-1;
start=0;
}
Arrays.fill(count2,0);
for(int i=start;i<=end;i++)
count2[s2.charAt(i)-'a']++;
if(Arrays.equals(count1,count2))
return true;
int tmp=j+len1-1;
for(start++,end++;end<len2&&end<=tmp;start++,end++){
count2[s2.charAt(end)-'a']++;
count2[s2.charAt(start-1)-'a']--;
if(Arrays.equals(count1,count2))
return true;
}
}
}
return false;
}
思路 3 plus plus：
??????上面算法虽然相比于之前的算法有了更好的运行效率。但是此算法的效率没有直接在字符串 s2 上采用滑动窗口的方法高，原因在于上面的算法在区间有重复计算和比较。在 s2 直接采用滑动窗口的算法参考如下：
public boolean checkInclusion(String s1, String s2) {
int n = s1.length(), m = s2.length();
if (n > m) {
return false;
}
int[] cnt1 = new int[26];
int[] cnt2 = new int[26];
for (int i = 0; i < n; ++i) {
++cnt1[s1.charAt(i) - 'a'];
++cnt2[s2.charAt(i) - 'a'];
}
if (Arrays.equals(cnt1, cnt2)) {
return true;
}
for (int i = n; i < m; ++i) {
++cnt2[s2.charAt(i) - 'a'];
--cnt2[s2.charAt(i - n) - 'a'];
if (Arrays.equals(cnt1, cnt2)) {
return true;
}
}
return false;
}
思路 4：
??????上面算法有一个缺点：因为 ct2 每次各增减一个字符的个数，但是却对 ct1 和 ct2 整体作比较，优化一下，那么需要用一个变量 diff 来表示 ct1 和 ct2 之间的差异性，如果 diff 为 0，则二者相等，返回 true；如果不相等，需要继续在 s2 上进行增减一个字符操作。差异性可以用 ct2 - ct1 得到，如果相减之后的数组元素均为 0，则二者相等，diff 也为0，否则初始时的 diff 为相减之后数组元素不为 0 的个数。
??????这个数组用 cnt 来表示。当结果返回 true 时对应的是 cnt 中的元素均为 0（diff 为 0），如果 cnt 中的数为负，意味 ct2 中的字符没有对应的 ct1 中的字符，则需要增加一个对应的字符；如果为正，意味着 ct2 中的字符是多余的，需要减去一个对应的字符。
??????在每次窗口滑动时，增加一个字符需要判断 cnt[该字符]+1 之后是否为 0，如果为 0，令 diff 减一；减少的字符同理。如果 diff 为 0，证明已找到结果了。
??????最终：参考算法：
public boolean checkInclusion(String s1, String s2) {
int len1=s1.length(),len2=s2.length();
if(len1>len2)
return false;
int[] cnt=new int[26];
int diff=0;
for(int i=0;i<len1;i++){
cnt[s2.charAt(i)-'a']++;
cnt[s1.charAt(i)-'a']--;
}
for(int i=0;i<cnt.length;i++)
if(cnt[i]!=0)
diff++;
if(diff==0)
return true;
for(int i=len1;i<len2;i++){
int addIndex=s2.charAt(i)-'a',minusIndex=s2.charAt(i-len1)-'a';
if(addIndex==minusIndex)
continue;
if(cnt[addIndex]==0)
diff++;
if(++cnt[addIndex]==0)
diff--;
if(cnt[minusIndex]==0)
diff++;
if(--cnt[minusIndex]==0)
diff--;
if(diff==0)
return true;
}
return false;
}
思路 5：
??????在思路 4 的基础上修改一下，用双指针的思路来做，初始时 left 和 right 指针均为 0，表示仅包含在 s2 上的第一个元素。初始化时 cnt 数组中的所有值要不为 0，要不小于 0（仅用 cnt[s1.charAt(i)-‘a’]–;来初始化）。
??????遍历：右指针一次遍历，增加的元素如果令对应 cnt 中的数为 <= 0，继续；如果 >0 时，则在当前左右指针所构成的区间中，当前元素是多余的，此时需要让左指针不断右移，去掉一个当前元素。
??????返回 true 的条件是：某一时刻 左右指针所构成的区间长度等于 s1。参考算法：
public boolean checkInclusion(String s1, String s2) {
int len1=s1.length(),len2=s2.length();
if(len1>len2)
return false;
int[] cnt=new int[26];
int left=0,right=0,addIndex;
for(int i=0;i<len1;i++)
cnt[s1.charAt(i)-'a']--;
while(right<len2){
addIndex=s2.charAt(right)-'a';
++cnt[addIndex];
while(cnt[addIndex]>0){
cnt[s2.charAt(left)-'a']--;
left++;
}
if(right-left+1==len1)
return true;
right++;
}
return false;
}
?????? 效率上，最后的双指针要优于之前的解法，算法也比较简洁。
总结
??????完。
|