本篇博客讲解LeetCode热题100道子串篇中的三道题 第一道:和为 K 的子数组 第二道:滑动窗口最大值 第三道:最小覆盖子串
class Solution {
public int subarraySum(int[] nums, int target) {
int count = 0;
for (int start = 0; start < nums.length; ++start) {
int sum = 0;
for (int end = start; end >= 0; --end) {
sum += nums[end];
if (sum == target) {
count++;
}
}
}
return count;
}
}
思想比较简单,找到所有子数组的和,如果等于目标值target。那么count++ 最终返回count
class Solution {
public int subarraySum(int[] nums, int target) {
int count = 0, pre = 0;
HashMap < Integer, Integer > map = new HashMap < > ();
map.put(0, 1);
for (int i = 0; i < nums.length; i++) {
pre += nums[i];
if (map.containsKey(pre - target)) {
count += map.get(pre - target);
}
map.put(pre, map.getOrDefault(pre, 0) + 1);
}
return count;
}
}
前缀和:是求解子数组的和等问题的好方法。通过累加数组中的值,使其减去数组中某个值来得到子数组的和。
前缀和用法示例:
建哈希表优化后。
前缀和: 使用pre += nums[i]; 用pre变量来累加前缀和。只需要pre即可。 因为我们只需要用累加和减去目标值target。再去哈希表中找有没有对应的值。 如果有对应的值,说明存在子数组的和为target。那么count++ 最终返回conunt
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
PriorityQueue<int[]> pQueue = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] pair1, int[] pair2) {
return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
}
});
for (int i = 0; i < k; ++i) {
pQueue.offer(new int[]{nums[i], i});
}
int[] ans = new int[n - k + 1];
ans[0] = pQueue.peek()[0];
for (int i = k; i < n; ++i) {
pQueue.offer(new int[]{nums[i], i});
while (pQueue.peek()[1] <= i - k) {
pQueue.poll();
}
ans[i - k + 1] = pQueue.peek()[0];
}
return ans;
}
}
pQueue
,用于存储滑动窗口内的元素。队列按照元素值降序排列,如果值相同则按索引降序排列。k
个元素加入队列。ans
,用于存储每个窗口的最大值。k
个元素开始,逐步将元素加入队列,并移除不在当前滑动窗口内的元素(根据索引判断)。使用优先队列高效地计算了数组中每个滑动窗口的最大值。
单调队列套路
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
Deque<Integer> deque = new LinkedList<Integer>();
for (int i = 0; i < k; ++i) {
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
}
int[] ans = new int[n - k + 1];
ans[0] = nums[deque.peekFirst()];
for (int i = k; i < n; ++i) {
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
while (deque.peekFirst() <= i - k) {
deque.pollFirst();
}
ans[i - k + 1] = nums[deque.peekFirst()];
}
return ans;
}
}
k
个元素,保持队列中元素对应的数组值按降序排列,并存储这些元素的索引。ans
并将第一个窗口的最大值(队列头部的元素)存入 ans
的第一个位置。ans
的相应位置。 最终返回结果数组 ans
。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] prefixMax = new int[n];
int[] suffixMax = new int[n];
for (int i = 0; i < n; ++i) {
if (i % k == 0) {
prefixMax[i] = nums[i];
}
else {
prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]);
}
}
for (int i = n - 1; i >= 0; --i) {
if (i == n - 1 || (i + 1) % k == 0) {
suffixMax[i] = nums[i];
} else {
suffixMax[i] = Math.max(suffixMax[i + 1], nums[i]);
}
}
int[] ans = new int[n - k + 1];
for (int i = 0; i <= n - k; ++i) {
ans[i] = Math.max(suffixMax[i], prefixMax[i + k - 1]);
}
return ans;
}
}
prefixMax[i]
表示从块的开始到索引 i
的最大值。suffixMax[i]
表示从索引 i
到块的结束的最大值。i
是块的开始,prefixMax[i]
等于 nums[i]
。prefixMax[i]
等于 prefixMax[i - 1]
和 nums[i]
的最大值。i
是块的结束,suffixMax[i]
等于 nums[i]
。suffixMax[i]
等于 suffixMax[i + 1]
和 nums[i]
的最大值。ans
数组,每个窗口的最大值是 suffixMax[i]
和 prefixMax[i + k - 1]
的最大值。ans
class Solution {
Map<Character, Integer> ori = new HashMap<Character, Integer>();
Map<Character, Integer> cnt = new HashMap<Character, Integer>();
public String minWindow(String s, String t) {
int tLen = t.length();
for (int i = 0; i < tLen; i++) {
char c = t.charAt(i);
ori.put(c, ori.getOrDefault(c, 0) + 1);
}
int l = 0, r = -1;
int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
int sLen = s.length();
while (r < sLen) {
++r;
if (r < sLen && ori.containsKey(s.charAt(r))) {
cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
}
while (check() && l <= r) {
if (r - l + 1 < len) {
len = r - l + 1;
ansL = l;
ansR = l + len;
}
if (ori.containsKey(s.charAt(l))) {
cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
}
++l;
}
}
return ansL == -1 ? "" : s.substring(ansL, ansR);
}
public boolean check() {
Iterator iter = ori.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Character key = (Character) entry.getKey();
Integer val = (Integer) entry.getValue();
if (cnt.getOrDefault(key, 0) < val) {
return false;
}
}
return true;
}
}
ori
哈希表记录字符串 t
中每个字符出现的次数。cnt
哈希表记录当前窗口中每个字符的出现次数。l
和右指针 r
,分别表示当前窗口的左右边界。len
和最小窗口的起始和结束位置 ansL
和 ansR
。t
中,将其加入 cnt
。t
中所有字符时,尝试缩小窗口: t
中,将其从 cnt
中移除。check
:
t
中所有字符,即 cnt
中每个字符的数量是否都不小于 ori
中对应的数量。