一、找到字符串中所有字母异位词
思路
字母异位词：当两个字符串每个字符的个数均相等时，一个字符串才是另一个字符串的异位词
p字符串长度固定，滑动固定窗口在 s 字符串中寻找子串，保存起始索引
使用存储法，保存p字符串中，每个字符出现的次数
再遍历窗口，直到 s 的最后一个子串
注意点：
循环前 保存窗口的前 p.length - 1 个字符
循环时，先统计 第 index + p.length 的字符，再与p统计的结果比较，确定是否异位
- 使用HashMap作存储容器
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int sLength = s.length();
int pLength = p.length();
List<Integer> ans = new ArrayList<>();
if(pLength <= sLength) {
Map<Character, Integer> pMemory = getMemoryMap(p, pLength);//p字符串的统计map
Map<Character, Integer> sMemory = getMemoryMap(s, pLength - 1);//s字符串中子串的统计map，[0, p.length() - 1]
int index = 0;//子串开始下标
while(index <= sLength - pLength) {//下标取值范围
char c = s.charAt(index + pLength - 1);
sMemory.put(c, sMemory.getOrDefault(c, 0) + 1);//当前子串的最后一位统计上
if(check(pMemory, sMemory)) {//比较是否异位
ans.add(index);
}
c = s.charAt(index);
sMemory.put(c, sMemory.get(c) - 1);//减去该下标的统计
++index;
}
}
return ans;
}
//默认从0下标开始到length - 1的字符统计
private Map<Character, Integer> getMemoryMap(String str, int length) {
Map<Character, Integer> memory = new HashMap<>();
for(int i = 0; i < length; i++) {
char c = str.charAt(i);
memory.put(c, memory.getOrDefault(c, 0) + 1);
}
return memory;
}
//以a map 作为标准去判断 b map 保存的键值对是否存在a map数值上的相等
private boolean check(Map<Character, Integer> a, Map<Character, Integer> b) {
for(Character c : a.keySet()) {
if(!a.get(c).equals(b.get(c))) {//因为是map，所以得到的是T：Integer，如果get出来就比较，两个Integer的 == 运算不严谨，需要使用equals方法
return false;
}
}
return true;
}
}
-
使用数组作存储容器
-
s和p仅包含小写字母
class Solution { public List<Integer> findAnagrams(String s, String p) { int sLength = s.length(); int pLength = p.length(); List<Integer> ans = new ArrayList<>(); if(pLength <= sLength) { int[] pMemory = getMemoryArray(p, pLength); int[] sMemory = getMemoryArray(s, pLength - 1); int index = 0; while(index <= sLength - pLength) { sMemory[s.charAt(index + pLength - 1) - 'a']++; if(Arrays.equals(pMemory, sMemory)) { ans.add(index); } sMemory[s.charAt(index) - 'a']--; ++index; } } return ans; } private int[] getMemoryArray(String str, int length) { int[] rs = new int[26]; for(int i = 0; i < length; i++) { rs[str.charAt(i) - 'a'] += 1; } return rs; } //以a数组为标准，检查b数组中所有的元素是否等于a数组 private boolean checkArray(int a[], int b[]) { for(int i = 0; i < a.length; i++) { if(a[i] != b[i]) { return false; } } return true; } } -
二、乘积小于K的子数组
-
暴力窗口枚举法
class Solution { public int numSubarrayProductLessThanK(int[] nums, int k) { int ans = 0; for(int i = 0; i < nums.length; i++) { int j = i; int acc = 1; while(j < nums.length && (acc *= nums[j]) < k) { ans++; j++; } } return ans; } } -
滑动窗口双指针
class Solution { public int numSubarrayProductLessThanK(int[] nums, int k) { if (k <= 1) return 0; int prod = 1, ans = 0, left = 0; for (int right = 0; right < nums.length; right++) { prod *= nums[right]; while (prod >= k) prod /= nums[left++]; ans += right - left + 1; } return ans; } }重点：ans += right - left + 1（当 left 移动完成后，对于当前的right，就包含了 right - left + 1 个乘积小于 k 的连续子数组：说是这么说，还得模拟一遍才有感觉）
每个元素都被乘上prod、后又被除去
三、长度最小的子数组
-
n个正整数的数组中 找出满足其和≥ target的长度最小的 连续子数组- 连续子数组，还得满足一个值，那么就是窗口中的所有元素的和
- 正整数，方便处理，当出现一个值使得窗口值大于等于 target，那么就可以求 该窗口的大小
class Solution { public int minSubArrayLen(int target, int[] nums) { int left = 0; int right = 0; int sum = 0;//窗口内和的大小 int ans = nums.length + 1;//结果初始值 while(right < nums.length) { sum += nums[right++];//将元素加入，扩大窗口 if(sum >= target) {//当和大于等于target就进入循环 while(sum >= target) {//一直缩小区间，减去左边元素值，直到小于target sum -= nums[left++]; } ans = Math.min(ans, (right - left + 1));//上述的操作将导致窗口值比真实的小1 } } return ans == nums.length + 1 ? 0 : ans;//当ans还是结果初始值，那么就是没有得到一个连续子数组，返回0 } }
