使用滑动窗口算法解决一些问题
在Leetcode上做到了一道题。
题目
给你两个长度相同的字符串，s 和 t。
将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。
用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。
如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。
如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。
解答
删去其中繁杂的题干，题意大概是从一个自然数串中，找出最长的和小于 maxCost 的串。此题可以用滑动窗口的思路解决。
滑动窗口
定义一个左指针 leftPtr，一个右指针 rightPtr ，开始时将两个指针都置于最左边。右侧指针每次向右移动一格，判断左指针所处的位置是否符合题意。如果不符合，将其向右移动，直到符合题意为止。存储最大的符合题意的距离，即为答案。
简单说来，可以理解成右指针拉着左指针向右动，它们之间用一根线（maxCost)相连。如果线足够长(rightPtr - leftPtr <= maxCost)，左指针就不会动，否则它也会跟着向右移。
代码
class Solution {
public int equalSubstring(String s, String t, int maxCost) {
int length = s.length();
int[] cost = new int[length];
for (int i = 0; i < length; i++) {
cost[i] = Math.abs(s.charAt(i) - t.charAt(i));
}
int rightPtr = 0, leftPtr = 0, max = 0, nowCost = 0;
while (rightPtr < length) {
nowCost += cost[rightPtr];
while (nowCost > maxCost) {
nowCost -= cost[leftPtr];
leftPtr++;
}
if (rightPtr - leftPtr + 1 > max) {
max = rightPtr - leftPtr + 1;
}
rightPtr++;
}
return max;
}
}