写一个java滑动窗口函数
时间: 2024-05-15 18:12:33 浏览: 9
以下是一个使用滑动窗口实现字符串匹配的Java函数示例:
```java
public static List<Integer> slidingWindow(String s, String pattern) {
List<Integer> result = new ArrayList<>();
if (s == null || s.length() == 0 || pattern == null || pattern.length() == 0) {
return result;
}
int[] freq = new int[256];
for (int i = 0; i < pattern.length(); i++) {
freq[pattern.charAt(i)]++;
}
int left = 0, right = 0, count = pattern.length();
while (right < s.length()) {
if (freq[s.charAt(right)] > 0) {
count--;
}
freq[s.charAt(right)]--;
right++;
if (count == 0) {
result.add(left);
}
if (right - left == pattern.length()) {
if (freq[s.charAt(left)] >= 0) {
count++;
}
freq[s.charAt(left)]++;
left++;
}
}
return result;
}
```
该函数使用两个指针 left 和 right,将字符串 s 分成一个个长度为 pattern.length() 的子串,然后检查每个子串是否包含与模式 pattern 相同的字符。具体实现中,使用一个数组 freq 来记录模式 pattern 中每个字符出现的次数,每次移动右指针 right 的时候,将对应字符出现的次数减一,并将 count(表示还需要匹配的字符数)减一;当 count 等于 0 时,说明找到了一个匹配的子串,将左指针 left 加入结果列表中;当右指针 right 和左指针 left 之间的距离等于 pattern.length() 时,说明当前子串已经检查完毕,需要移动左指针 left 并恢复对应字符出现的次数和 count 的值。
该函数的时间复杂度为 O(n),其中 n 为字符串 s 的长度,因为每个字符最多只会被访问两次。