当前位置：首页 > news >正文

Hot100速刷计划day04（10-12）

news 2024/10/24 13:34:29

Hot100速刷计划day04（10-12）

10 和为k的子数组

时间复杂度：O(n)

class Solution {public int subarraySum(int[] nums, int k) {int []s = new int[nums.length+1];s[0] = 0;for (int i = 0; i < nums.length; i++) {s[i+1] = nums[i] + s[i];}int count = 0;HashMap<Integer,Integer> map = new HashMap<>(s.length);for (int sj : s) {count+=map.getOrDefault(sj-k,0);map.merge(sj,1,Integer::sum);}return count;}
}

妙处

采用了前缀和思想，用n的时间做了原本n^2的事
采用hashmap来再次缩短时间
采用hashmap的api来简化代码

（ps：解法来自灵神）

代码解释：

Map<Integer, Integer> cnt = new HashMap<>(n + 1); // 设置容量可以快 2ms

定义一个哈希表 cnt：用于存储不同的前缀和出现的次数。键是前缀和的值，值是该前缀和出现的次数。
new HashMap<>(n + 1)：n 是数组的长度，n + 1 用来预分配哈希表的初始容量，这样可以减少哈希表扩容带来的性能损耗，从而提高效率（快大约 2 毫秒）。

for (int sj : s) {ans += cnt.getOrDefault(sj - k, 0);cnt.merge(sj, 1, Integer::sum); // cnt[sj]++
}

1. 遍历数组 `s`:

sj 是当前的前缀和。

2. 查找 `sj - k` 是否存在:

cnt.getOrDefault(sj - k, 0)：这里通过前缀和的性质，如果当前的前缀和 sj 减去 k 得到的前缀和 sj - k 已经出现在 cnt 中，说明存在一个子数组的和为 k。因此，通过 cnt.getOrDefault(sj - k, 0) 获取 sj - k 出现的次数，并累加到 ans 上。
ans += cnt.getOrDefault(sj - k, 0)：累加满足条件的子数组个数。

3. 更新哈希表：

cnt.merge(sj, 1, Integer::sum)：这是 HashMap 的 merge 方法，用于将当前的前缀和 sj 插入到哈希表中。
- 如果 sj 已经存在，则将其值（出现次数）加 1。
- 如果 sj 不存在，则插入 sj，并将其对应的值设为 1。
- Integer::sum 是 Java 的方法引用，表示两个整数相加的操作。

关键思想：

前缀和：通过记录数组中每一位的累积和（前缀和），可以将问题转化为在数组中寻找某个差值的过程。
哈希表：使用哈希表来存储和查询前缀和，能够使查询 sj - k 是否存在的操作时间复杂度降为 O(1)。

具体逻辑：

我们遍历数组中的每个元素，累积计算当前的前缀和 sj。
然后，我们使用哈希表快速查询前缀和 sj - k 是否已经存在（即是否存在一个子数组的和为 k）。
最后，我们将当前前缀和 sj 的出现次数记录到哈希表 cnt 中。

11 滑动窗口的最大值

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;int []ans = new int[n-k+1];//最终答案总的数量Deque<Integer>deque = new ArrayDeque<>();for (int i = 0; i < n; i++) {//入(保持单调性[单调递减])while (!deque.isEmpty()&&nums[deque.getLast()]<nums[i]){deque.removeLast();}deque.addLast(i);//出(i和deque里面的第一个元素的差距大于k个)if(i-deque.getFirst()>=k){deque.removeFirst();}//记录答案(保证这个索引是合法的（前面k个还尚未构成完整的队列）)//也就是窗口没满if(i >= k-1){ans[i-k+1] = nums[deque.getFirst()];}}return ans;}
}

这个是一个单调队列的模版，用于处理类似的问题

要点

此处的单调队列是单调递减的
要多熟悉基础api的用法（map，set，deque），java还是有很多很方便的api的

12 最小覆盖子串

时间复杂度：O(n+m)

class Solution {public String minWindow(String s, String t) {//s是长串，t是模版串//特殊情况处理int [] cnt_father = new int[128];int [] cnt_son = new int[128];//左右边界指针int ansLeft = -1;int ansRigth = s.length();int left = 0;for (int i = 0; i < t.length(); i++) {cnt_son[t.charAt(i)]++;}for (int i = 0; i < s.length(); i++) {cnt_father[s.charAt(i)]++;while (isCovered(cnt_father,cnt_son)){if(ansRigth - ansLeft > i - left){ansLeft = left;ansRigth = i;}cnt_father[s.charAt(left)]--;left++;}}//这个鲁棒性的判定设计够我学一年啊return ansLeft < 0 ? "":s.substring(ansLeft,ansRigth+1);}public boolean isCovered(int [] father,int [] son){for (int i = 0; i < father.length; i++) {if(father[i] < son[i])return false;}return true;}
}