在使用Redis Cache时,需要注意以下几点:
“滑动窗口算法通常用于解决数组或字符串中的连续子数组或子字符串问题,它可以通过维护一个窗口来减少不必要的计算。
思路:
使用两个指针来定义一个窗口,一个指针指向窗口的左边界,另一个指针指向窗口的右边界。我们还需要一个哈希表来记录窗口中每个字符出现的次数。
实现步骤:
代码实现:
public int shortestSubstring(String s, Set<Character> chars) {
// 将Set<Character>转换为字符数组
char[] charArray = new char[chars.size()];
int i = 0;
for (char c : chars) {
charArray[i++] = c;
}
// 初始化哈希表
Map<Character, Integer> charCount = new HashMap<>();
for (char c : charArray) {
charCount.put(c, 0);
}
// 初始化指针和变量
int left = 0, right = 0;
int minLen = Integer.MAX_VALUE;
int missingCount = charCount.size(); // 记录窗口中缺少的字符数量
// 移动右指针,直到窗口中包含所有字符
while (right < s.length()) {
char c = s.charAt(right);
if (charCount.containsKey(c)) {
charCount.put(c, charCount.get(c) + 1);
if (charCount.get(c) == 1) {
missingCount--;
}
}
right++;
// 移动左指针,直到窗口中不再包含所有字符
while (missingCount == 0) {
minLen = Math.min(minLen, right - left);
c = s.charAt(left);
if (charCount.containsKey(c)) {
charCount.put(c, charCount.get(c) - 1);
if (charCount.get(c) == 0) {
missingCount++;
}
}
left++;
}
}
return minLen;
}