滑动窗口

用i,j表示滑动窗口的左边界和右边界，通过改变i,j来扩展和收缩滑动窗口，可以想象成一个窗口在字符串上游走，当这个窗口包含的元素满足条件，即包含字符串T的所有元素，记录下这个滑动窗口的长度j-i+1，这些长度中的最大/小值就是要求的结果。

• 不断增加j使滑动窗口增大，直到窗口包含了T的所有元素

• 不断增加i使滑动窗口缩小，满足条件之后，这个时候不能需要再去递减窗口，记录此时滑动窗口的长度，并保存最大/小值

• 让i再增加一个位置，这个时候滑动窗口肯定不满足条件了，那么继续从步骤一开始执行，寻找新的满足条件的滑动窗口，如此反复，直到j超出了源字符串S范围。

// 首先明确一点(left, right]为所求区间
func module(nums []int) {
	n := len(nums)
	// 左指针
  left := -1
	
  // 记录最短区间长度
	res := n + 1
	
	for right := 0; right < n; right++ {
		// 加入nums[i]之前，(left, right - 1]可能不满足条件
		// 1. 直接将A[i]加到区间，形成(left, right]
		// 2. 更新区间状态
		for 区间超出/满足条件 {
			res = min(res, right - left)
			// 3. 移除nums[++left]
			// 4. 更新区间的状态
		}
		// assert 区间(left, right]到这里肯定不满足条件
	}
	return	res
}

最长区间

无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

• java

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s==null||s.length()==0) return 0;
        Set<Character> set =new HashSet<>();
        int f=0,l=0,max=Integer.MIN_VALUE;
       while(f<s.length()&&l<s.length()){
            if(!set.contains(s.charAt(f))){
                set.add(s.charAt(f++));
                max=Math.max((f-l),max);
            }else{
                set.remove(s.charAt(l++));
            }
        }
        return max;
    }
}

• Go

func lengthOfLongestSubstring(s string) int {
   left,N:=-1,len(s)
	res:=0
	windows:=make(map[byte]int,0)
	for reight:=0;reight<N;reight++ {
		windows[s[reight]]++
		for windows[s[reight]]>1{
			left++
			windows[s[left]]--
		}
		res=func(a,b int) int{
			if a>b{
			return a
		}
			return b
		}(res,reight-left)
	}
	return res
}

最长连续1的个数

给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。
返回仅包含 1 的最长（连续）子数组的长度。

• java

class Solution {
    public int longestOnes(int[] nums, int k) {
    int l=0,r=0,max=0,count=0;
    while(r<nums.length){
        if(nums[r++]==0){
            count++;
        }
        while (count>k){
            if(nums[l++]==0){
                count--;
            }
        }
        max=Math.max(max,r-l);
    }
    return max;
    }
}

• Go

func longestOnes(nums []int, k int) int {
   l,r,c,m:=0,0,0,0
   for l<len(nums){
       if nums[l]==0 {
           c++
       }
       l++
       for c>k {
           if nums[r]==0{
               c--
           }
           r++
       }
       m=func(x,y int)int{
           if x>y {
               return x
           }
           return y
       }(m,l-r)
   }
   return m
}

最短区间

长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和≥ target的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

• java

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int sum=0,l=0,minLen=Integer.MAX_VALUE;
        for(int r=0;r<nums.length;r++){
            sum+=nums[r];
            while(sum>=target){
                minLen=Math.min(minLen,r-l+1);
                sum-=nums[l++];
            }
        }
        return minLen==Integer.MAX_VALUE?0:minLen;
    }
}

• Go

func minSubArrayLen(target int, nums []int) int {
   sum,mlen,l:=0,100000000,0
	for a:=0;a<len(nums);a++{
		sum+=nums[a]
		for sum>=target {
			mlen=func(x,y int)int{
				if x<y {
					return x
				}
				return y
			}(a-l+1,mlen)
			sum=sum-nums[l]
			l++
		}
	}
	if mlen==100000000{
        return 0
    }
    return mlen

}

定长区间 (窗口大小一般为待检索的子区间，需要做到同步滑动-- ++)

找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

• java

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
      int sl=s.length() ,pl=p.length();
      if(sl<pl){
          return new ArrayList();
      }
      List<Integer> ans=new ArrayList();
      int[] sd=new int[26];
      int[] pd=new int[26];
      for(int i=0;i<pl;i++){
          ++sd[s.charAt(i)-'a'];
          ++pd[p.charAt(i)-'a'];
      }
      if (Arrays.equals(sd,pd)){
          ans.add(0);
      }
      for(int i=0;i<sl-pl;i++){
          --sd[s.charAt(i)-'a'];
          ++sd[s.charAt(pl+i)-'a'];
        if (Arrays.equals(sd,pd)){
             ans.add(i+1);
        }
      }
      return ans;
    }
}

参考资料

• B站刷题视频