目录

思想

案例

连续元素最大之和

题目

分析

解法

求相同字母异序词的下标

题目

分析

解法

思想

滑动窗口是指一个窗口，在一段区间上从左到右滑动,一直到区间的尾部,滑动窗口的长度是可以动态变化的(也可以固定)。一般情形下可以使用两个指针分别指向窗口的两边,指针 i 指向窗口的左边界,指针 j 指向窗口的右边界

一些情况下，使用滑动窗口处理字符串和数组 能提高效率,减少循环的嵌套使用，降低时间复杂度

滑动窗口在网络、大数据、流量控制等都有应用。

下面将简单介绍使用滑动窗口处理字符串和数组的案例

案例

连续元素最大之和

题目

有一个整型数组，给定一个正整数k,求数组里连续k个数之和的最大值

Input : arr[] = {100, 200, 300, 400}  k = 2

Output : 700

Input : arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}  k = 4

Output : 39

Input : arr[] = {2, 3} k = 3 Output : Invalid 

分析

上述问题能想到的最简单的解法就是遍历整个数组，从下标为0开始，每次循环获取k个连续的元素，计算其和之后比较获得最大的和，这样一来需要两次循环(一层遍历数组，一层遍历k个元素)。

我们可以使用滑动窗口来简化代码，因为k是给定的固定值，所以窗口大小是固定的，相当于窗口向右滑动的时候，只需要减去左侧的值(被移除窗口范围的旧值)，再加上右侧的值(新移入窗口范围的元素)，就可以得到新的连续K个数之和，遍历之后就能得到最大值，只需要一层遍历就足够了

解法

public void cal(int[] array, int k) {if (array.length == 0 || k <= 0 || k > array.length) {System.out.println("Invalid");return;}int maxSum = 0;//计算初始窗口位置的K个数之和for (int i = 0; i < k; i++) {maxSum += array[i];}int windows_sum = maxSum;for (int i = 1; i <= array.length - k; i++) {windows_sum = windows_sum - array[i - 1] + array[k + i - 1];if (windows_sum > maxSum) {maxSum = windows_sum;}}System.out.println("result= " + maxSum);}

求相同字母异序词的下标

题目

给定一个字符串s,和一个非空字符串p,要求寻找在s中所有和p满足相同字母异序词的子串(s,p全都是由26个小写英文字母组成，并且长度不大于20100)，并返回对应的子串的第一个字符的下标

Input: s: "cbaebabacd" p: "abc"

Output: [0, 6]

分析

要求找到相同字母异序词，只需要子串里各个字母的个数相同即可。

1.使用map集合来表示子串，key为26个英文字母，value为每个字母对应的个数

2.使用int数组来表示子串(每个元素表示对应字母的个数,第一个元素表示’a’的个数，第二个表示’b’的个数，以此类推…)，每次滑动的时候判断目标窗口和滑动窗口里的int数组是否一致

解法

解法一:

使用map里记录每个子串里的每个字母的元素个数，由于采用判断map是否有该元素的方式来加快遍历速度，故每次判断字母后需要减去1，每结束一次循环判断还需要还原现场(把map还原成初始状态initMap)

 public static List findAnagrams(String s, String p) {List result = new ArrayList();if (s == null || p == null || p.length() > s.length()) {return result;}Map map = new HashMap();initMap(p, map);int windowsLen = p.length();//代表左右窗口指针int left = 0;int right = left + windowsLen - 1;while (right < s.length()) {boolean flag = true;List list = new ArrayList();for (int i = right; i >= left; i--) {char c = s.charAt(i);Integer count = map.get(c);//i对应的字母不在目标串里,因为两个子串的长度一致，故所有包含i上的字母的子串都不满足条件if (count == null || count == 0) {left = i + 1;right = left + windowsLen - 1;flag = false;break;} else {map.put(c, map.getOrDefault(c, 0) - 1);//把在比较过程中满足的字母存在list里(因为这里在比较字符串的时候采用相减的方式而不是==)list.add(c);}}//如果退出时，flag表示整个窗口的元素都在map里，说明满足条件if (flag == true) {result.add(left);left++;right = left + windowsLen - 1;}//还原现场，让map的数据保持和p的组成一致for (Character c : list) {map.put(c, map.getOrDefault(c, 0) + 1);}}return result;}private static void initMap(String p, Map map) {map.clear();for (char c : p.toCharArray()) {map.put(c, map.getOrDefault(c, 0) + 1);}}

解法二:

上述代码比较繁琐，解法二使用int数组，直接比较数组，逻辑上更加清晰

public List findAnagrams(String s, String p) {List ans = new ArrayList<>();if (s.length() < p.length()) {return ans;}int[] dict = new int[26];//使用26长度的整型数组来表示给定字符串p的组成for (char c : p.toCharArray()) {dict[c - 'a']++;}//用来记录滑动窗口里的字符串的组成int[] cur = new int[26];for (int i = 0; i < p.length() ; i++) {cur[s.charAt(i) - 'a']++;}for (int i = p.length() ; i < s.length(); i++) {if (isSame(dict, cur)) {ans.add(i - p.length() );}cur[s.charAt(i - p.length() ) - 'a']--;cur[s.charAt(i) - 'a']++;}return ans;}//判断两个int数组是否一致private boolean isSame(int[] a, int[] b) {for (int i = 0; i < 26; i++) {if (a[i] != b[i]) {return false;}}return true;}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！