算法-滑动窗口类型

6666

滑动窗口

1、大小为K的最大和子数组

给定一个数组，找出该数组中所有大小为“K”的连续子数组的平均值。

让我们用实际输入来理解这个问题:

Array: [1, 3, 2, 6, -1, 4, 1, 8, 2], K=5

1、对于前5个数字(索引0-4的子数组)，平均值为:(1 + 3 + 2 + 6?1)/ 5 = > 2.2
2、对于前5个数字(索引1-5的子数组)，平均值为:(3 + 2 + 6-1 + 4) / 5 = > 2. 8
....

Output: [2.2, 2.8, 2.4, 3.6, 2.8]

按照蛮力算法，时间复杂度O(N*K)

  public static double[] findAverages(int k, int[] arr) {
      double[] result = new double[arr.length - k + 1];
      for (int i = 0; i <= arr.length - k; i++) {
          double sum = 0;
          for (int j = i; j < i + k; j++) {
              sum += arr[j];
          }
          result[i] = sum / k;
      }
      return result;
  }

滑动窗口,时间复杂度O(N)

public static double[] findAveragesV1(int k, int[] arr) {
    double[] result = new double[arr.length - k + 1];
    double windowSum = 0;
    int windowStart = 0;
    for (int windowEnd = 0; windowEnd < arr.length; windowEnd++) {
        windowSum += arr[windowEnd];
        if (windowEnd >= k - 1) {
            result[windowStart] = windowSum / k;
            windowSum -= arr[windowStart];
            windowStart++;
        }
    }
    return result;
}

2、给定和的最小子数组

给定一个正数数组和一个正数’ S ‘，求和大于等于’ S '的最小连续子数组的长度。如果不存在子数组，则返回0。

Input: [2, 1, 5, 2, 3, 2], S=7 
Output: 2
Explanation: The smallest subarray with a sum great than or equal to '7' is [5, 2].

这个问题遵循滑动窗口模式，我们可以使用类似于在大小k的最大和子数组中讨论的策略。但有一个区别:在这个问题中，滑动窗口的大小不是固定的。我们将如何解决这个问题:

• 首先，我们将从数组开始的元素相加，直到它们的总和大于或等于’ S '。
• 这些元素将构成我们的滑动窗口。我们被要求找到总和大于或等于S的最小窗口。我们将这个窗口的长度记为到目前为止最小的窗口。
• 在此之后，我们将继续在滑动窗口中添加一个元素(即向前滑动窗口)，以逐步的方式。
• 在每一步中，我们也会尝试从一开始就缩小窗口。我们将缩小窗口，直到窗口的和再次小于’ S '。这是需要的，因为我们打算找到最小的窗口。这种收缩也将分多个步骤进行;在每一步中，我们将做两件事:
  1、检查当前窗口长度是否为迄今为止最小的，如果是，则记住其长度。
  2、从运行和中减去窗口的第一个元素以缩小滑动窗口。

public static int findMinSubArray(int s, int[] arr) {
    int windowSum = 0, minLength = Integer.MAX_VALUE;
    int windowStart = 0;
    for (int windowEnd = 0; windowEnd < arr.length; windowEnd++) {
        windowSum += arr[windowEnd];
        while (windowSum >= s) {
            minLength = Math.min(minLength, windowEnd - windowStart + 1);
            windowSum -= arr[windowStart];
            windowStart++;
        }
    }
    return minLength == Integer.MAX_VALUE ? 0 : minLength;
}

上述算法的时间复杂度为O(N)。外部for循环运行所有元素，而内部while循环只处理每个元素一次，因此算法的时间复杂度为O(N+N)渐近等价于O (N)。

3、具有K个不同字符的最长子串

给定一个字符串，找出其中最长的子字符串的长度，且不超过K个不同的字符。

Input: String="araaci", K=2
Output: 4
Explanation: The longest substring with no more than '2' distinct characters is "araa".

这个问题遵循滑动窗口模式，我们可以使用与给定和的最小子数组中讨论的类似的动态滑动窗口策略。我们可以使用HashMap来记住我们处理过的每个字符的频率。我们将如何解决这个问题:

• 首先，我们将从字符串的开头插入字符，直到HashMap中有“K”个不同的字符。
• 这些字符将构成我们的滑动窗口。我们被要求找到不超过“K”个不同字符的最长窗口。我们将把这个窗口的长度记为迄今为止最长的窗口。
• 在此之后，我们将继续在滑动窗口中添加一个字符(即向前滑动窗口)，以逐步的方式。
• 在每一步中，如果HashMap中不同字符的计数大于“K”，我们将尝试从一开始就缩小窗口。我们将缩小窗口，直到HashMap中的不同字符不超过“K”个。这是需要的，因为我们打算找到最长的窗口。
• 在收缩时，我们将减少字符走出窗口的频率，并在其频率变为零时将其从HashMap中删除。
• 在每一步结束时，我们将检查当前窗口的长度是否是到目前为止最长的，如果是，则记住它的长度。

public static int findLength(String str, int k) {
    if (str == null || str.length() == 0 || str.length() < k) {
        throw new IllegalArgumentException();
    }
    int windowStart = 0, maxLength = 0;
    Map<Character, Integer> charFrequencyMap = new HashMap<>();
    for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
        char rightChar = str.charAt(windowEnd);
        charFrequencyMap.put(rightChar, charFrequencyMap.getOrDefault(rightChar, 0) + 1);
        while (charFrequencyMap.size() > k) {
            char leftChar = str.charAt(windowStart);
            charFrequencyMap.put(leftChar, charFrequencyMap.get(leftChar) - 1);
            if (charFrequencyMap.get(leftChar) == 0) {
                charFrequencyMap.remove(leftChar);
            }
            windowStart++;
        }
        maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
    }
    return maxLength;

}

上述算法的时间复杂度为O(N)，其中’ N '是输入字符串中的字符数。外部的for循环运行所有字符，而内部的while循环只处理每个字符一次，因此算法的时间复杂度将为O(N+N)渐近等价于O (N)。

4、篮子里的水果

给定一个字符数组，其中每个字符代表一棵果树，给你两个篮子，你的目标是在每个篮子里放入最大数量的水果。唯一的限制是每个篮子只能放一种水果。 你可以从任何一棵树开始，但是一旦你开始了，你就不能跳过一棵树。你会从每棵树上摘一个水果，直到你摘不动为止，也就是说，当你不得不摘第三种水果时，你会停下来。 编写一个函数返回两个篮子中水果的最大数量。

Input: Fruit=['A', 'B', 'C', 'A', 'C']
Output: 3
Explanation: We can put 2 'C' in one basket and one 'A' in the other from the subarray ['C', 'A', 'C']

这个问题遵循滑动窗口模式，非常类似于具有K个不同字符的最长子字符串。在这个问题中，我们需要找到不超过两个不同字符(或水果类型!)的最长子数组的长度。这将当前问题转换为具有K个不同字符的最长子串，其中K=2。

public static int findLength(char[] arr) {
      int windowStart = 0, maxLength = 0;
      Map<Character, Integer> fruitFrequencyMap = new HashMap<>();
      for (int windowEnd = 0; windowEnd < arr.length; windowEnd++) {
          fruitFrequencyMap.put(arr[windowEnd], fruitFrequencyMap.getOrDefault(arr[windowEnd], 0) + 1);
          while (fruitFrequencyMap.size() > 2) {
              fruitFrequencyMap.put(arr[windowStart], fruitFrequencyMap.get(arr[windowStart]) - 1);
              if (fruitFrequencyMap.get(arr[windowStart]) == 0) {
                  fruitFrequencyMap.remove(arr[windowStart]);
              }
              windowStart++;
          }
          maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
      }
      return maxLength;
  }

5、不重复的子串

给定一个字符串，找出不包含重复字符的最长子字符串的长度。

Input: String="aabccbb"
Output: 3
Explanation: The longest substring without any repeating characters is "abc".

这个问题遵循滑动窗口模式，我们可以使用与K个不同字符的最长子串中讨论的类似的动态滑动窗口策略。我们可以使用HashMap来记住我们处理过的每个字符的最后一个索引。每当我们得到一个重复的字符，我们将收缩滑动窗口，以确保我们总是有不同的字符在滑动窗口。

public static int findLength(String str) {
    int windowStart = 0, maxLength = 0;
    Map<Character, Integer> charIndexMap = new HashMap<>();
    for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
        char rightChar = str.charAt(windowEnd);
        if (charIndexMap.containsKey(rightChar)) {
            windowStart = Math.max(windowStart, charIndexMap.get(rightChar) + 1);
        }
        charIndexMap.put(rightChar, windowEnd);
        maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
    }
    return maxLength;
}

上述算法的时间复杂度为O(N)，其中’ N '是输入字符串中的字符数。

6、替换后具有相同字母的最长子串

给定一个只有小写字母的字符串，如果你被允许用任何字母替换不超过’ k '个字母，找出替换后具有相同字母的最长子字符串的长度。

Input: String="aabccbb", k=2
Output: 5
Explanation: Replace the two 'c' with 'b' to have a longest repeating substring "bbbbb".

这个问题遵循滑动窗口模式，我们可以使用与No-repeat Substring中讨论的类似的动态滑动窗口策略。我们可以使用HashMap来计算每个字母出现的频率。 我们将遍历字符串，在窗口中每次添加一个字母。我们还将跟踪任何窗口中最大重复字母的计数(我们将其称为maxRepeatLetterCount)。所以在任何时候，我们知道我们可以有一个窗口，其中有一个字母重复maxRepeatLetterCount次，这意味着我们应该尝试替换剩余的字母。如果我们有超过k个剩余字母，我们应该缩小窗口，因为我们不允许替换超过k个字母。

public static int findLength(String str, int k) {
    int windowStart = 0, maxLength = 0, maxRepeatLetterCount = 0;
    Map<Character, Integer> letterFrequencyMap = new HashMap<>();
    for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
        char rightChar = str.charAt(windowEnd);
        letterFrequencyMap.put(rightChar, letterFrequencyMap.getOrDefault(rightChar, 0) + 1);
        maxRepeatLetterCount = Math.max(maxRepeatLetterCount, letterFrequencyMap.get(rightChar));

        if (windowEnd - windowStart + 1 - maxRepeatLetterCount > k) {
            char leftChar = str.charAt(windowStart);
            letterFrequencyMap.put(leftChar, letterFrequencyMap.get(leftChar) - 1);
            windowStart++;
        }
        maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
    }
    return maxLength;
}

上述算法的时间复杂度为O(N)，其中’ N '是输入字符串中的字母数。

7、替换后带有1的最长子数组

给定一个包含0和1的数组，如果你被允许用1替换不超过k个0，找出全部为1的最长连续子数组的长度。

Input: Array=[0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1], k=2
Output: 6
Explanation: Replace the '0' at index 5 and 8 to have the longest contiguous subarray of 1s having length 6.

这个问题遵循滑动窗口模式，非常类似于替换后具有相同字母的最长子字符串。唯一的区别是，在这个问题中，我们在输入数组中只有两个字符(1和0)。 按照类似的方法，我们将遍历数组，每次在窗口中添加一个数字。我们还将跟踪当前窗口中重复1的最大数量(我们将其称为maxOnesCount)。所以在任何时候，我们知道我们可以有一个有15个重复maxOnesCount时间的窗口，所以我们应该尝试替换剩下的0。如果我们有超过k个剩余的0，我们应该缩小窗口，因为我们不允许替换超过k个0。

public static int findLength(int[] arr, int k) {
    int windowStart = 0, maxLength = 0, maxOnesCount = 0;
    for (int windowEnd = 0; windowEnd < arr.length; windowEnd++) {
        if (arr[windowEnd] == 1) {
            maxOnesCount++;
        }

        if (windowEnd - windowStart + 1 - maxOnesCount > k) {
            if (arr[windowStart] == 1) {
                maxOnesCount--;
            }
            windowStart++;
        }
        maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
    }
    return maxLength;
}

上述算法的时间复杂度为 O(N)，其中’ N '是输入数组中数字的计数。