怎么查看什么公司做的网站,宿迁网站建设公司排名,360怎么做网站搜索,腾讯公众微信号和为 K 的子数组#xff08;mid#xff09;
给你一个整数数组 nums 和一个整数 k #xff0c;请你统计并返回 该数组中和为 k 的子数组的个数 。 子数组是数组中元素的连续非空序列。 输入#xff1a;nums [1,1,1], k 2 输出#xff1a;2 解法1#xff1a;前缀和Map 这…和为 K 的子数组mid
给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的子数组的个数 。 子数组是数组中元素的连续非空序列。 输入nums [1,1,1], k 2 输出2 解法1前缀和Map 这是一道经典的前缀和运用题。 统计以每一个 nums[i] 为结尾和为 k 的子数组数量即是答案。 我们可以预处理前缀和数组 prefix对于求解以某一个 nums[i] 为结尾的和为 k 的子数组数量本质上是求解在 [0,i] 中prefix 数组中有多少个值为 prefix[i]−k 的数这可以在遍历过程中使用「哈希表」进行同步记录。 是以当前节点为结尾的计算不是以当前节点为起始的计算
public int subarraySum(int[] nums, int k) {int len nums.length;int[] prefix new int[len];prefix[0] nums[0];for (int i1; ilen; i){prefix[i] prefix[i-1]nums[i];}MapInteger,Integer map new HashMap();//当子串的起始节点为0即取前缀和的整段而不做截断//需要插入一个长度为0的子串map.put(0,1);int res 0;for(int i0; ilen; i){res map.getOrDefault(prefix[i]-k,0);map.put(prefix[i],map.getOrDefault(prefix[i],0)1);}return res;
}滑动窗口最大值hard
给你一个整数数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 输入nums [1,3,-1,-3,5,3,6,7], k 3 输出[3,3,5,5,6,7] 解释 滑动窗口的位置 最大值 [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 解法1滑动窗口最优 假设我们当前处理到某个长度为 k 的窗口此时窗口往后滑动一格会导致后一个数新窗口的右端点添加进来同时会导致前一个数旧窗口的左端点移出窗口。 随着窗口的不断平移该过程会一直发生。若同一时刻存在两个数 nums[j] 和 nums[i]ji所在一个窗口内下标更大的数会被更晚移出窗口此时如果有 nums[j]nums[i] 的话可以完全确定 nums[j] 将不会成为后续任何一个窗口的最大值此时可以将必然不会是答案的 nums[j] 从候选中进行移除。 不难发现当我们将所有必然不可能作为答案的元素即所有满足的小于等于 nums[i] 移除后候选集合满足「单调递减」特性即集合首位元素为当前窗口中的最大值为了满足窗口长度为 k 的要求在从集合头部取答案时需要先将下标小于的等于的 i−k 的元素移除。 为方便从尾部添加元素从头部获取答案我们可使用「双端队列」存储所有候选元素。 用一个容器充当窗口保持它存储的元素是单调非递增这样它的第一个元素就是容器中的最大值最后一个就是最小值根据前面的分析向右滑动过程中如果遇到了更大的元素就可以把在容器中小于它的元素都移除掉因为后加入的更大的元素才可能成为容器中的最大值。因为第一个元素是最大值我们需要能够获取它所以这是一个先入先出的容器这里用队列就可以了。它的思路与单调栈一样但只不过用队列来当容器这便是“单调队列”了。
public int[] maxSlidingWindow(int[] nums, int k) {DequeInteger stack new ArrayDeque();int[] res new int[nums.length-k1];for(int i0; inums.length; i){// 队列中的下标是小于新加入的i那么如果[i] 队尾// 说明队尾肯定不会是窗口里的一个最大值了// 从队尾开始把小于[i]的都移除掉。// 这样就能保证队列的值是一个单调非递减队列了while(!stack.isEmpty() nums[stack.peekLast()]nums[i]){stack.pollLast();}stack.addLast(i);if(ik-1){// 现在的队首就是窗口中的最大值res[i-k1] nums[stack.peekFirst()];// 再把左滑出窗口的最大值从队列中移除因为它已被滑出窗口了if(stack.peekFirst()k-1 i) stack.pollFirst();}}return res;
}解法2优先队列
public int[] maxSlidingWindow(int[] nums, int k) {// 使用优先队列大顶堆来存储窗口中的索引以便快速找到最大值PriorityQueueInteger pq new PriorityQueue((a, b) - nums[b] - nums[a]);// 初始化结果数组长度为 nums 数组长度减去窗口大小 k 再加 1int[] res new int[nums.length - k 1];for (int i 0; i nums.length; i) {// 将当前索引 i 加入优先队列pq.add(i);// 当索引 i 大于 k-1 时说明窗口已经滑动了至少 k 次可以开始记录最大值if (i k - 1) {// 记录窗口内的最大值即优先队列中索引对应的值res[i - k 1] nums[pq.peek()];// 清除出窗口的元素即索引小于 i-k1 的元素while (!pq.isEmpty() pq.peek() i - k 1) {pq.poll();}}}// 返回结果数组包含了每个窗口的最大值return res;
}最小覆盖字串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 “” 。 对于 t 中重复字符我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串我们保证它是唯一的答案。 输入s “ADOBECODEBANC”, t “ABC” 输出“BANC” 解释最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。 解法1滑动窗口
public String minWindow(String s, String t) {// 初始化一个足够大的数组来计数字符假设字符集大小为70A-Z的大小写int[] cnt new int[70];// 标记是否找到有效子串boolean flag false;// 遍历字符串 t对每个字符进行计数并将对应的数组元素减1for (int i 0; i t.length(); i) {char c t.charAt(i);cnt[c - A]--; // 将字符转换为0-65的整数便于在数组中索引}// 初始化结果字符串为 s假设没有找到更小的子串String res s;// 初始化左右指针int l 0, r 0;// 滑动窗口的右边界while (r s.length()) {// 将 s 的当前字符计数加1cnt[s.charAt(r) - A];// 当前窗口包含 t 的所有字符时尝试收缩左边界while (l r check(cnt)) {// 标记已找到有效子串flag true;// 更新最小窗口String tmp s.substring(l, r 1);res tmp.length() res.length() ? tmp : res;// 移动左边界将 l 所指的字符从计数器中减去cnt[s.charAt(l) - A]--;l;}// 扩展右边界继续寻找可能的最小子串r;}// 如果找到了有效子串返回 res否则返回空字符串return flag ? res : ;
}// 检查数组中的所有计数是否都大于等于0即 s 的当前窗口是否包含 t 的所有字符
public boolean check(int[] arr) {for (int i 0; i arr.length; i) {if (arr[i] 0)return false; // 如果有字符计数小于0则当前窗口不包含 t 的所有字符}return true; // 所有字符计数都非负说明当前窗口包含 t 的所有字符
}定义两个长度为 60足够存下所有字母种类的数组 c1 和 c2用于存储字符频率。其中 c1 用于记录字符串 t 中字符的频率c2 用于记录当前滑动窗口内字符的频率。 设定好字母与频率数组下标的映射关系小写字母 a-z 对应下标 0-25大写字母 A-Z 对应下标 26-51。 使用变量 tot 来记录还需要匹配的字符种类数当 tot 0 代表当前滑动窗口对应的子串能够实现对 t 的覆盖即任意字符满足 c2[i]≥c1[i]。 使用双指针 j 和 i 表示滑动窗口的左右边界。从前往后遍历字符串 s在每个位置上更新字符频率数组 c2。若 c2 中字符的频率达到了 c1 中的字符频率则将 tot 减 1表示一个字符已经匹配完成。 每当右边界往后移动一步之后滑动窗口会增加一个字符。此时我们检查左边界能否右移同时不会使得 tot 变大。即每次右边界右移后我们检查左边界 c2[j]c1[j] 是否满足
若满足说明当前左边界指向字符并非必须当前子串 s[j…i] 必然不是最短子串。我们让左边界 j 进行右移并重复进行左边界 c2[j]c1[j] 的检查直到窗口不能再收缩若不满足说明当前窗口没有任何一个后缀字符串能够实现对 t 的覆盖我们并不能对窗口实现收缩
每次对窗口移动完成后我们检查当前 tot 是否为 0对字符串 t 的覆盖是否完成若为 0 则尝试用当前窗口对应的字符串 s[j…i] 更新 ans。
class Solution {public String minWindow(String s, String t) {int n s.length(), tot 0;int[] c1 new int[60], c2 new int[60];for (char x : t.toCharArray()) {if (c1[getIdx(x)] 1) tot;}String ans ;for (int i 0, j 0; i n; i) {int idx1 getIdx(s.charAt(i));if (c2[idx1] c1[idx1]) tot--;while (j i) {int idx2 getIdx(s.charAt(j));if (c2[idx2] c1[idx2] --c2[idx2] 0) j;else break;}if (tot 0 (ans.length() 0 || ans.length() i - j 1)) ans s.substring(j, i 1);}return ans;}int getIdx(char x) {return x A x Z ? x - A 26 : x - a;}
}
