站长之家ppt素材,做网站与网页有什么区别,wordpress设置缓存,职业中学网站建设这里是Themberfue 和为 K 的子数组 题目解析 返回子数组中所有元素的和等于给定k的个数。 算法讲解 这题好像是用滑动窗口解决#xff0c;但其实不能#xff0c;因为 nums 中的元素可能存在负数#xff0c;就不能保证其单调性的性质。 用前缀和求也不易想到#xff0c;… 这里是Themberfue 和为 K 的子数组 题目解析 返回子数组中所有元素的和等于给定k的个数。 算法讲解 · 这题好像是用滑动窗口解决但其实不能因为 nums 中的元素可能存在负数就不能保证其单调性的性质。 · 用前缀和求也不易想到但是我们应该换个角度看问题既然是某一段的和这一段的起点可能是从0开始也可能不从0开始。 · 也就是说要想满足题目要求的话那么就构成一个等式当前 i 的前缀和减去 k 肯定等于i 前些前缀和的某个前缀和。 · 如图所示也就是若出现让这个等式成立的情况那么从 0 到 i 这一范围内肯定存在满足题目要求的子数组可能不止一个。 · 所以我们借助哈希表解题并将当前 i 的前缀和以及出现的次数的存入哈希表中若该哈希表中存在 前缀和 - k那么就让计数器加上其出现的次数。 · 细节 1. 前缀和为0时其次数应该初始化为1因为可能存在 sum - k 0的情况这也是满足题目条件的。 2. 我们不用真的创建一个前缀和数组只需要维护一个 sum 就好然后将当前的 sum 加入到哈希表中即可。 编写代码
class Solution {public int subarraySum(int[] nums, int k) {// 创建哈希表标记前缀和出现的次数MapInteger, Integer hash new HashMap();hash.put(0, 1);int sum 0, count 0;for (int i 0; i nums.length; i) {sum nums[i];count hash.getOrDefault(sum - k, 0);hash.put(sum, hash.getOrDefault(sum, 0) 1);}return count;}
}
和可被 K 整除的子数组 题目解析 返回子数组中所有元素的和可以被k整除的个数。 算法讲解 · 本题借助一个数学定理解题会更方便 同余定理 · 假设两数字 i 和 j这两数的差除以任一数若可以整除得到 k。即 (i - j) / p k ...... 0 · 则 i % p j % p · 利用这一定理便可求解出题目思路和上一题差不多。 · 细节对于负数的取余需要作特殊情况。 编写代码
class Solution {public int subarraysDivByK(int[] nums, int k) {// 存放前缀和的余数以及出现的次数MapInteger, Integer hash new HashMap();hash.put(0, 1);// 根据同余定理int sum 0, count 0;for (int x: nums) {sum x; // 计算当前位置的前缀和int mod (sum % k k) % k; // Java取模的特殊性当被除数为负数时取模结果为负数需要纠正count hash.getOrDefault(mod, 0);hash.put(mod, hash.getOrDefault(mod, 0) 1);}return count;}
}
连续数组 题目解析 这是一个只含 0 和 1 的数组找到数组中 0 和 1 数量相同的子数组返回最长子数组的长度 算法讲解 · 既然是相同数量的 0 和 1如果把 0 都变成 -1那么相同数量 0 和 1 的子数组的和就一定是 0 · 利用这一性质i 下标的前缀和若与之前下标的前缀和相同则存在这样的子数组更新长度。 · 即 sum - x 0 编写代码
class Solution {public int findMaxLength(int[] nums) {// 存放前缀和和对应的下标MapInteger, Integer hash new HashMap();hash.put(0, -1); // 前缀和为0所对应的下标应该为-1// 转化为和为0的子数组int sum 0, len 0; for (int i 0; i nums.length; i) {sum nums[i] 0 ? -1 : 1; // 将所有的0转化为-1// 不需要每次都更新key为sum的值只需更新一次即可if (hash.containsKey(sum)) len Math.max(len, i - hash.get(sum)); // 存在与当前sum相同的前缀和则更新数据else hash.put(sum, i); // 不存在则将其放入哈希表}return len;}
}
矩阵区域和 题目解析 求出 (i - k, j - k) 到 (i k, j k) 之间的和即可。 算法讲解 · 本题使用二维前缀和首先根据公式创建出前缀和数组。 · 随后根据题目要求求出 x1x2y1y2坐标。 · 最后带入公式即可。 · 细节注意下标映射关系以及边界处理。 编写代码
class Solution {public int[][] matrixBlockSum(int[][] mat, int k) {// 创建dp二维前缀和数组int m mat.length 1, n mat[0].length 1;int[][] dp new int[m][n];for (int i 1; i m; i) {for (int j 1; j n; j) {dp[i][j] dp[i - 1][j] dp[i][j-1] mat[i - 1][j - 1] - dp[i-1][j-1];}}int[][] answer new int[m - 1][n - 1];for (int i 0; i m - 1; i) {for (int j 0; j n - 1; j) {int x1 Math.max(i - k, 0), x2 Math.min(i k, m - 2);int y1 Math.max(j - k, 0), y2 Math.min(j k, n - 2);answer[i][j] dp[x2 1][y2 1] - dp[x1][y2 1] - dp[x2 1][y1] dp[x1][y1];}}return answer;}
} 好了以上就是今天内容的全部讲解如果有不懂的地方随时私聊 我们下一章节见 位运算
