7. 双指针、滑动窗口
7.1 含有全部字符的最短字符串
1. 题目
https://leetcode.cn/problems/minimum-window-substring/
给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。如果 s 中存在多个符合条件的子字符串，返回任意一个。
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
2. 思路
想法1：滑动窗口+hash数组
通过滑动的窗口（两个指针）来判断窗口切割出来的s的子字符串是否包含了t。
包含函数：考虑到字符A-Z ... a-z只有58个字符，用两个数组分别表示t的字符和当前窗口的字符，如果相等返回真(O(1)复杂度，长度固定58)。
想法2：diff来代表区别
s=XX⋯XABCXXXX，t=ABC，那么显然 [XX⋯XABC] 是第一个得到的可行区间。
按照之前的逻辑需要我们求X⋯XABC，然后⋯XABC等等。
思考有没有一种方法来让让他直接找到ABC？
通过diff代表两个数组的差值，如果减去的数对于diff无影响就不做比较。
3. 代码
想法1：
public String minWindow(String s, String t) {
int[] standard = new int[asc]; // A~Z: 65~90, a~z: 97~122
int[] curWindow = new int[asc];
int sLen = s.length();
int tLen = t.length();
if(sLen < tLen){
return "";
}
// hash数组初始化
for(int i = 0; i < tLen;i++){
standard[t.charAt(i)-'A']++;
curWindow[s.charAt(i)-'A']++;
}
if(isContain(standard,curWindow))
return s.substring(0,tLen);
// 开始窗口的遍历
int l = 0;
int r = tLen-1;
int I = 0;
int J = 0;
int min = Integer.MAX_VALUE;
// 右侧扩容
while(r < sLen){
if(isContain(standard,curWindow)){
if(r-l+1 < min){
min = r-l+1;
I = l;
J = r;
}
curWindow[s.charAt(l)-'A']--;
l++;
}else{
r++;
if(r >= sLen) continue;
int temp = s.charAt(r)-'A';
curWindow[temp]++;
}
}
if(min == Integer.MAX_VALUE) return "";
return s.substring(I,J+1);
}
// 包含函数
public boolean isContain(int[] standard, int[] curWindow){
int n = standard.length;
for(int i = 0; i <58; i++){
if(standard[i] != 0 && curWindow[i] < standard[i]){
return false;
}
}
return true;
}
7.2 验证回文串II
1. 题目
https://leetcode.cn/problems/valid-palindrome-ii/
给你一个字符串 s，最多 可以从中删除一个字符。
请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。
输入：s = "aba"
输出：true
输入：s = "abca"
输出：true
解释：你可以删除字符 'c' 。
输入：s = "abc"
输出：false
2. 思路
想法（错误）：左右指针探测：如果遇到不同的值，左面看下一个是否一样，右面看下一个是否一样，哪个不一样删那个。
但是有问题：
"cuucu"应该删最右侧的u，但是按照探测，删了c
于是解法为删掉c或者u（l，r位置），分别看其是否是回文，如果有一个是就是，都不是说明该字符串不是回文。
3. 代码
public boolean validPalindrome(String s) {
int l = 0;
int r = s.length()-1;
while(l <= r){
if(s.charAt(l) == s.charAt(r)){
l++;
r--;
}else{
return isPal(s,l+1,r) || isPal(s,l,r-1);
}
}
return true;
}
public boolean isPal(String s,int l,int r){
int sLen = s.length();
if(l < 0 || r >= sLen){
return false;
}
while(l <= r){
if(s.charAt(l) == s.charAt(r)){
l++;
r--;
}else{
return false;
}
}
return true;
}
7.3 中心扩散法
中心扩散
遍历字符串，取每一个字符为一个回文子串的中心
按照回文串的要求向两边扩散，统计回文串个数
上述情况 只有当回文子串的中心只有一个字符时可行
所以还需考虑回文子串中心有两个字符时的情况
可以在遍历的时候，取每个字符计数的同时
再取该字符与下一个字符同时作为中心，向两边扩散统计回文串个数
1. 题目
https://leetcode.cn/problems/a7VOhD/
给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
2. 思路
想法1：暴力三个循环，能过但是不太行。
解法：中心扩散法，一个for循环遍历每一个位置。假设某个位置为i，从i开始左右分别探测，找有几个回文。
注意点：中心可能为一个也可能为两个，可以遍历两次或者通过如下方式解决：
遍历中心位置（一个和两个的情况）
长度为4的情况下，中心位置情况如下
编号i 左中心 右中心
0 0 0
1 0 1
2 1 1
3 1 2
4 2 2
5 2 3
6 3 3
观察可得到长度为2n-1（0-6有7个），左为i/2，右为(i+1)/2
3. 代码
public int countSubstrings(String s) {
int sLen = s.length();
int ans = 0;
// 遍历中心点位置
for(int i = 0; i < sLen*2-1; i++){
int l = i/2;
int r = (i+1)/2;
// 向外扩散
while(l>= 0 && r < sLen && s.charAt(l) == s.charAt(r)){
ans++;
l--;
r++;
}
}
return ans;
}
7.4 连续子数组数量
1. 题目
给定一个数组，请你编写一个函数，返回元素乘积末尾零数量大于等于x的连续子数组数量。
答案可能太大，请将答案对10^9+7取模再返回。
数组长度不超过10^5。
数组元素、x均为不超过10^9的正整数。
2. 思路
首先是滑动窗口找连续子数组
对于从left开始的情况， 看有多少组符合条件的解：len-right种，其中right为满足条件的右边界
但是由于窗口过大，导致long也不够用，需要优化。
注意到10只能由2和5分解得到，所以找数组中2,5出现的次数即可
注意一个数不一定只能出现一个2/5，比如50，里面有1个2和2个5
3. 代码
public int getSubarrayNum (ArrayList<Integer> a, int x) {
// write code here
int left = 0, right = 0;
int len = a.size();
long ans = 0;
if (len == 0) return 0;
// 从left开始，最多有多少可能
// 到right是他区间的最小值
// len-right
int twoTime = 0;
int fiveTime = 0;
twoTime += isNeed(a.get(0),2);
fiveTime+= isNeed(a.get(0),5);
while (right < len) {
if (twoTime >= x && fiveTime >= x && left <= right) {
ans += (len - right);
ans %= (1e9 + 7);
int cur = a.get(left);
twoTime-= isNeed(cur,2);
fiveTime-= isNeed(cur,5);
left++;
System.out.println("left: "+left);
} else {
right++;
if(right < len){
int cur = a.get(right);
twoTime += isNeed(cur,2);
fiveTime += isNeed(cur,5);
}
}
}
ans %= (1e9 + 7);
return (int)ans;
}
// a中有b的几次方
public int isNeed(int a, int b) {
int i = 0;
while(a % b == 0){
a /= b;
i++;
}
return i;
}
7.5 统计完全子数组的数目--优雅
1. 题目
https://leetcode.cn/problems/count-complete-subarrays-in-an-array/
给你一个由 正 整数组成的数组 nums 。
如果数组中的某个子数组满足下述条件，则称之为 完全子数组 ：
- 子数组中 不同 元素的数目等于整个数组不同元素的数目。
返回数组中 完全子数组 的数目。
子数组 是数组中的一个连续非空序列。
示例 1：
输入：nums = [1,3,1,2,2]
输出：4
解释：完全子数组有：[1,3,1,2]、[1,3,1,2,2]、[3,1,2] 和 [3,1,2,2] 。
示例 2：
输入：nums = [5,5,5,5]
输出：10
解释：数组仅由整数 5 组成，所以任意子数组都满足完全子数组的条件。子数组的总数为 10 。
2. 思路
经典的滑动窗口问题，枚举右指针，如果满足就让左缩小。
hashmap的意义：总的没有意义，set也行，主要是为了size，cur是为了动态缩减大小。
这里的写法比上面优雅很多。
3. 代码
class Solution {
public int countCompleteSubarrays(int[] nums) {
HashMap<Integer,Integer> map = new HashMap<>();
HashMap<Integer,Integer> cur = new HashMap<>();
// 遍历求不同数的个数,其实set就可以
for(int i = 0; i < nums.length; i++){
map.put(nums[i],map.getOrDefault(nums[i],0)+1);
}
int size = map.size();
int ans = 0;
int left = 0;
// 枚举右端点
for(int right = 0; right < nums.length; right++){
// 加入
cur.put(nums[right],cur.getOrDefault(nums[right],0)+1);
// 一直减少窗口，直到不等，继续循环
while(cur.size() == size){
ans += (nums.length - right);
int curL = cur.get(nums[left]);
if(curL <= 1) cur.remove(nums[left]);
else cur.put(nums[left],curL-1);
left++;
}
}
return ans;
}
}