)
打卡第七天
2道中等题
class Solution {
public:int equalSubstring(string s, string t, int maxCost) {int n = s.length();vector<int> diff(n, 0);//创建数组存储s和t对应位置字符的ASCII码差值for (int i = 0; i < n; i++) {diff[i] = abs(s[i] - t[i]);}int maxLength = 0;//初始化最大长度为0int start = 0, end = 0;//首尾指针初始都为0int sum = 0;while (end < n) {//遍历,从0到n-1sum += diff[end];while (sum > maxCost) {//超过最大成本,右移窗口sum -= diff[start];start++;}maxLength = max(maxLength, end - start + 1);end++;}return maxLength;}
};
算法思路总结：
1.首先计算字符串s和t每个对应位置字符的ASCII码差值
2.使用滑动窗口&双指针,end指针向右移动，扩大窗口,当窗口内差值总和超过maxCost时，start指针向右移动，收缩窗口.
3.在满足条件（总和≤maxCost）的窗口中，记录最大长度
滑动窗口&双指针区别:
「滑动窗口」是固定大小的，「双指针」是不固定大小的；
「滑动窗口」一定是同向移动的，「双指针」可以相向移动。
「滑动窗口」是一类问题本身，「双指针」是解决一类二分查找问题的通用优化方法。
耗时≈1.5小时 明天继续