Hot100速刷计划day04(10-12)
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;}
}
妙处
- 将是否有重合转换为数组之间的关系
- 将异常的检测用一个标志变量和一个三元运算符解决(主要是ansLeft的判断–>没有满足条件的情况就一直设置为-1)
(ps:解法来自灵神)