算法学习笔记（一）：滑动窗口和双指针
滑动窗口套路：
核心套路三步骤：
1.入： 下标为 i 的元素进入窗口，更新相关统计量(因为一个元素进入了，则相关统计的数据要更新，就是+)，然后进行判断，如果i < k - 1 则continue，继续进入窗口，因为定长窗口元素不足；
2.更新：更新答案。一般是更新最大\最小值；
3.出：下标为i - k + 1 的元素离开窗口，更新相关统计量(出了一个元素，窗口内的统计量要减去这个出的元素)。
一：定长滑动窗口
1.定长字串中元音的最大数目
元音有：a\e\i\o\u
给你字符串 S 和整数 k；
请你返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。
class Solution {
public int maxVowels(String s, int k) {
int max = Integer.MIN_VALUE;
int sum = 0;
char[] arr = s.toCharArray();
for (int i = 0; i < arr.length; i++) {
//入
if (isVowel(arr[i])) sum++;
if (i < k - 1) continue;
//更新
max = Math.max(sum, max);
//出
char out = arr[i - k + 1];
if (isVowel(out)) sum--;
}
return max;
}
public boolean isVowel(char ch) {
return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
}
}2.子数组最大平均数I
给你一个由 n 个元素组成的整数数组 nums 和一个整数 k
请你找出平均数最大且长度为 k 的连续子数组，并输出该最大平均值
任何误差小于 10(-5)的答案都将被视为正确答案
class Solution {
public double findMaxAverage(int[] nums, int k) {
int maxAvg = Integer.MIN_VALUE, sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (i < k - 1) continue;
maxAvg = Math.max(maxAvg, sum);
sum -= nums[i - k + 1];
}
return 1.0 * maxAvg / k;
}
}3.大小为 k 且平均值大于等于阈值的子数组数目
给你一个整数数组 arr 和两个整数 k 和threshold
请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。
class Solution {
public int numOfSubarrays(int[] arr, int k, int threshold) {
int avg = 0, count = 0;
for (int i = 0; i < arr.length; i++) {
avg += arr[i];
if (i < k - 1) continue;
if (avg / k >= threshold) count++;
avg -= arr[i - k + 1];
}
return count;
}
}4.得到 K 个黑块的最少涂色次数
给你一个长度为 n 下标从 0 开始的字符串 blocks，blocks[i] 要么是 ‘W’ 要么是 ‘B’，表示白色和黑色
给你一个整数 k，表示想要连续黑色快的数目
每一次操作中，你可以选择一个白色快将它涂成黑色快
请你返回至少出现一次连续 k个黑色快的最少操作次数
class Solution {
public int minimumRecolors(String blocks, int k) {
int min = Integer.MAX_VALUE, count = 0;
char [] arr = blocks.toCharArray();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 'W') count++;
if (i < k - 1) continue;
min = Math.min(min, count);
char out = arr[i - k + 1];
if (out == 'W') count--;
}
return min;
}
}二：不定长滑动窗口
1.无重复字符的最长字串
给定一个字符串 s，请你找出其中不含有重复字符的最长字串的长度。
class Solution {
public int lengthOfLongestSubstring(String s) {
//用哈希表或者数组存重复字符的上一个索引
Map<Character, Integer> map = new HashMap<>();
char[] arr = s.toCharArray();
int left = -1; //开始从-1开始 表示没有重复元素
int len = 0;
for (int i = 0; i < arr.length; i++) {
if (map.containsKey(arr[i])) { //有重复的 那么就将left起点从上一个重复的为止开始算长度
left = Math.max(left, map.get(arr[i])); //这是防止多个重复 比如 abba b先重复了 left已经再1了 这个时候a
//重复了 a的上一个位置还在0 但是不能从0开始算 要从1开始算
}
//更新最新字符的索引
map.put(arr[i], i);
len = Math.max(len, i - left);
}
return len;
}
}2.每个字符最多出现两次的最长子字符串
给你一个字符串 s，请找出满足每个字符最多出现两次的最长子字符串
并返回该子字符串的最大长度
class Solution {
public int maximumLengthSubstring(String s) {
//这特么是简单题？
/**
不定长滑动窗口 因为这题说了是由小写字母组成 可以用阿斯克吗来做
或者用哈希？
想一想哈希的做法
*/
// Map<Character, Integer> map = new HashMap<>();
// int len = 0, left = 0;
// char[] arr = s.toCharArray();
// for (int i = 0; i < arr.length; i++) {
// map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
// while (map.get(arr[i]) > 2) {
// //去掉重复字符的第一个
// map.put(arr[left], map.get(arr[left]) - 1);
// left++;
// }
// len = Math.max(len, i - left + 1);
// }
// return len;
//用数组来做 效率一点
int[] arr = new int[26];
char[] c = s.toCharArray();
int len = 0, left = 0;
for (int i = 0; i < c.length; i++) {
int j = c[i] - 'a'; //正好对应索引下标a从0开始
arr[j]++;
while (arr[j] > 2) {
arr[c[left++] - 'a']--; //不管元素是什么，只要保证left从0开始遍历，一直到找到j这个元素 然后删掉它
//这个时候的left++就是新的开端 就是找到第一个重复的元素 删掉他 然后从它下一个开始
}
len = Math.max(len, i - left + 1);
}
return len;
}
}3.删掉一个元素以后全为 1 的最长子数组
给你一个二进制数组 nums，你需要从中删掉一个元素
请你在删掉元素的结果数组种，返回最长的且只包含1的非空子数组的长度
如果不存在这样的子数组，请返回0
class Solution {
public int longestSubarray(int[] nums) {
int len = 0, sum = 0, left = 0;
for (int i = 0; i < nums.length; i++) {
sum += 1- nums[i]; //如果是0 那么肯定是+1了 相当于判断是否是0
while (sum > 1) {
//表示最少进来了两个0了，那么需要删掉最开始的那个0
sum -= 1- nums[left++];
}
len = Math.max(len, i - left);
}
return len;
}
}二.相向双指针
两个指针left=0，right = n - 1，从数组的两端开始，向中间移动，这叫相向双指针。
1.反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用0(1)的额外空间解决
这一问题
class Solution {
public void reverseString(char[] s) {
/**
双指针？ 从左和从右开始同时移动，然后右边和左边的值互换
然后当左>=右了就停下
*/
int left = 0, right = s.length - 1;
while (left < right) {
char temp = s[left];
s[left++] = s[right];
s[right--] = temp;
}
}
}2.验证回文串
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读
和反着读都一样。则可以认为改短语是一个 回文串
字母和数字都属于字母数字字符
给你一个字符串 s，如果它是回文串，返回true，否则返回false
class Solution {
public boolean isPalindrome(String s) {
//先大写转小写， 然后去掉非字母数字字符 用ascii码
//字母ASCII码是97-122 数字0-9的ASCII码是48到57
s = s.toLowerCase();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if ((c >= 48 && c <= 57) || (c >= 97 && c <= 122)) {
sb.append(c);
}
}
//验证回文串
int left = 0, right = sb.length() - 1;
String str = sb.toString();
while (left < right) {
char c = str.charAt(left);
if (str.charAt(left++) != str.charAt(right--)) return false;
}
return true;
}
}3.删除字符串两端相同字符后的最短长度
给你一个只包含字符 ‘a’、‘b’、'c' 的字符串 s，你可以执行下面这个操作任意次：
1.选择字符串 s的一个非空的前缀，这个前缀的所有字符都相同
2.选择字符串 s的一个非空的后缀，这个后缀的所有字符都相同
3.前缀和后缀在字符串种任意位置都不能有交集
4.前缀和后缀包含的所有字符都要相同
5.同时删除前缀和后缀
请你返回堆字符串 s 执行上面操作任意次以后(可能是0次)，能得到的最短长度
class Solution {
public int minimumLength(String s) {
/**
就是前后消消乐，只要前后有相同的字符就全删掉，然后没有相同了就返回剩下的字符串长度
双指针，前后相同的话，left++ 一直到不相同或者left和right相遇了
同理 right-- 一直到不相同或者和left相遇
最后计算right和left的长度+1 因为是表示索引 length是相减+1
*/
int left = 0, right = s.length() - 1;
while (left < right && s.charAt(left) == s.charAt(right)) {
char c = s.charAt(left);
while (left <= right && s.charAt(left) == c) left++;
while (left <= right && s.charAt(right) == c) right--;
}
return right - left + 1;
}
}4. 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回每个数字的平方组成的新数组，
要求也按 非递减顺序 。
class Solution {
public int[] sortedSquares(int[] nums) {
int left = 0, right = nums.length - 1;
int[] arr = new int[nums.length];
for (int i = nums.length - 1; i >= 0; i--) {
int l = nums[left] * nums[left];
int r = nums[right] * nums[right];
if (l > r) {
arr[i] = l;
left++;
} else {
arr[i] = r;
right--;
}
}
return arr;
}
}5.两数之和II -输入有序数组
给你一个下标从 1 开始的证书数组 numbers，该数组已按 非递减顺序排列，请你从数组种
找到满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1]
和 numbers[index2]，则 1<= index1 < index2 <= numbers.length
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2
你可以假设每个输入 只对应唯一的答案，而且你 不可以重复使用相同的元素
你所涉及的解决方案必须只能使用常量级的额外空间。
class Solution {
public int[] twoSum(int[] numbers, int target) {
//使用哈希
// Map<Integer, Integer> map = new HashMap<>();
// for (int i = 0; i < numbers.length; i++) {
// int right = target - numbers[i];
// if (map.containsKey(right)) {
// return new int[]{i + 1, map.get(right)};
// }
// map.put(numbers[i], i + 1);
// }
// return null;
//优化 因为是需要输出有序
int left = 0, right = numbers.length - 1;
int[] arr = new int[2];
while (left < right) {
int temp = numbers[left] + numbers[right];
if (target == temp ) break;
if (temp < target) {
left++;
} else {
right--;
}
}
arr[0] = left + 1;
arr[1] = right + 1;
return arr;
}
}6.平方数之和
给定一个非负整数 c，判断是否存在两个整数 a 和 b，使得 a2 + b2 = c
class Solution {
public boolean judgeSquareSum(int c) {
//想象成两数之和 用c的根作为基数来判断
int a = 0, b = (int)Math.sqrt(c);
while (a <= b) {
if (a * a == c - b * b) return true;
if (a * a < c - b * b) {
a++;
} else {
b--;
}
}
return false;
}
}7.统计和小于目标的下标对数目
给你一个下标从 0 开始长度为 n的整数数组 nums 和一个整数target，请你返回
满足 0 <= i < j < n且 nums[i] + nums[j] < target的下标对(i, j) 的数目
class Solution {
public int countPairs(List<Integer> nums, int target) {
//因为只是输出对数 不需要index 所以排序之和不影响
Collections.sort(nums);
int count = 0, left = 0, right = nums.size() - 1;
while (left < right) {
if (nums.get(left) + nums.get(right) < target) {
//因为排序了 所以这个区间内的对数都满足
count += right - left;
left++;
} else {
right--;
}
}
return count;
}
}8.三数之和
给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足
i != j、i != k 且 j != k，满足还满足 nums[i] + nums[j] + nums[k] == 0。
请你返回所有和为 0 且不重复的三元组、
注意：答案中不可以包含重复的三元组。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
/**
固定指针+双指针 从0开始 然后left=i+1 right = n-1
先排序
接下来就是先判断重复的情况
i = i + 1 则continue i++
left = left +1 left++
right = right-1 right--
然后满足 i+left+right = 0 left++ right--
如果 < 0 left++ >0 right--
*/
List<List<Integer>> lists = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0 ) return lists;
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[left]);
list.add(nums[right]);
lists.add(list);
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return lists;
}
}三.同向双指针
两个指针的移动方向相同
1.最短无序连续子数组
给你一个整数数组 nums，你需要找出一个连续子数组，如果对这个子数组进行升序排序，
那么整个数组都会变成升序排序
请你找出符合题意得 最短 子数组，并输出它得长度。
class Solution {
public int findUnsortedSubarray(int[] nums) {
/**
边界双指针解法
可以把数组抽象成三段，前、中、后
前的长度>=0 这段肯定是有序的
中的长度>=0 这段肯定是无序的
后的长度>=0 这段肯定是有序的
目的就是找出中段的长度 最极限的情况就是要么是0要么是整个数组的length
怎么确定中段范围呢，找出两个临界值 begin和end
从begin开始，begin前面的都是比begin小的，begin后面的begin+1肯定是大于begin的 无序的开始
然后到end结束，end后面的肯定都是比end大的
然后中段的长度就是end-begin+1 算长度都需要+1
begin从右到左遍历 确定begin的位置
end从左到右遍历 确定end的位置
*/
int len = nums.length;
int min = nums[len - 1], begin = 0;
int max = nums[0], end = -1;
for (int i = 0; i < len; i++) {
//从左右到算end
if (nums[i] < max) {
end = i;
} else {
max = nums[i];
}
//从右到左算begin
if (nums[len - i - 1] > min) {
begin = len - i - 1;
} else {
min = nums[len - i - 1];
}
}
return end - begin + 1;
}
}四.双序列双指针
1.合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1和nums2，另外有两个整数 m 和 n，分别
表示 nums1和nums2中的元素数目
请你合并 nums2到nums1中，使得合并后的数组同样按 非递减顺序 排列
注意：最终合并后的数组不应由函数返回，而是存储在nums1中，为了应对这种情况
nums1的初始长度为m+n，其中前m个元素表示应合并的元素，后n个元素为0
应忽略，nums2的长度为n。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
/**
因为nums1和nums2已经是递增排序过了的
所以换个角度，从大到小开始插入，因为nums1的后面肯定是空的 所以从尾部插入大的
谁大先插入谁 然后指针--
*/
int a = m - 1, b = n - 1;
int max = m + n - 1;
while (b >= 0) { //因为是nums2插入nums1所以最后结束肯定nums已经空了才算完成插入
//大的插入
if (a >= 0 && nums1[a] > nums2[b]) {
nums1[max--] = nums1[a--];
} else {
nums1[max--] = nums2[b--];
}
}
}
}2.判断子序列
给定字符串 s 和 t，判断s是否为 t的子序列
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符
相对位置形成的新字符串
例如：“ace”是“ancde”的一个子序列，而“aec”并不是
class Solution {
public boolean isSubsequence(String s, String t) {
/**
双指针 一个从s0开始 一个从t0开始
相等 都++
不等 s原地等候 t++
最后s=s.length或者t=t.length退出循环
最后判断 s==s.length ==就是走完了 那么肯定是字串
*/
int sIndex = 0, tIndex = 0;
while (sIndex < s.length() && tIndex < t.length()) {
if (s.charAt(sIndex) == t.charAt(tIndex)) {
sIndex++;
tIndex++;
} else {
tIndex++;
}
}
return sIndex == s.length();
}
}原文地址：https://blog.csdn.net/Ice166/article/details/143834347
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！