昆明好的网站开发公司,宣传视频,半岛网,asp汽车驾驶培训学校网站源码560. 和为 K 的子数组 给你一个整数数组 nums 和一个整数 k #xff0c;请你统计并返回 该数组中和为 k 的连续子数组的个数 。 示例 1#xff1a; 输入#xff1a;nums [1,1,1], k 2 输出#xff1a;2 示例 2#xff1a; 输入#xff1a;nums [1,2,3], k 3 输出请你统计并返回 该数组中和为 k 的连续子数组的个数 。 示例 1 输入nums [1,1,1], k 2 输出2 示例 2 输入nums [1,2,3], k 3 输出2 比较容易想到的是暴力解法我承认我想不到。为了不遗漏的得到每个连续子数组的和即为了得到所有 nums 中下标范围为 i~j 的区间的和0ijnums.length 直接双重遍历即可。 public int subarraySum(int[] nums, int k) {int count 0;// i 为起点遍历 j 时得到以 i 为起点的每个连续子数组的和// i 遍历了整个数组也就是说每个点作为起点的连续子数组都试过了所以没有遗漏的情况// 比如 nums 为 [1,2,3]// sum 尝试了 1,12,123// 然后尝试了 2,23// 最后尝试了 3我还是不理解我为什么想不到暴力解法for (int i 0; i nums.length; i) {int sum 0;for (int j i; j nums.length; j) {sum nums[j];if (sum k) {count;}}}return count;}使用前缀和哈希表优化前缀和的思想其实早就学过。比如数列前两项的和 S2 为 n1n2前四项的和 S4 为 n1n2n3n4如果问你 n3n4 为多少你可以发现就是 S4-S2即 ni…nj Si-S(j-1)。前缀和就是用一个数组 ss[n] 保存了数组 nums 前 n-1 位的和比如 nums 为 [1,2,3]s[3] 保存了 nums 的前两位的和即为 123。如果让你求 s[4] 你只需要 s[3] nums[2] 即可。插一嘴得到前缀和数组的公式 int[] s new int[nums.length1];// 正常来说应该是 s[i] s[i-1] nums[i] // 但是数组下标从 0 开始for(int i0;inums.length;i){s[i1] s[i]nums[i]}首先再解读一下题目题目要求可以理解为 ni…nj k 这样的 i 和 j 有几对。而暴力解法的短处在于先遍历 i 视为当前 i 已确定此时再加一重遍历视为 j 也确定然后遍历 j 时就能不断得到 ni..nj, ni...n(j1)...然后统计遍历过程中有几个和等于 k 即可。但是现在有了前缀和数组就当做数列和 S 好了你会发现既然我们要求 ni…nj那么遍历前缀和数组时其实就相当于确定了 j也就是说此时我们得到的是 Sj而 k ni..nj Sj - S(i-1) 也就是说只要存在 S(i-1) Sj - k那么这样的 i 有几个就表示 ni…nj k 这样的 i 和 j 有几对或者说当 j 确定时也就是 Sj 确定时等于 Sj - k 的前缀和有几个就表示 ni…nj k 这样的 i 和 j 有几对。比如当前前缀和为 5k 为 2那 5 前面有几个前缀和等于 3 就表示我能得到几个 2 了反证一下比如 n1n2n3n4 5, n1n2 3那么就有 n3n4 这样的连续和为 2为了记录某个前缀和有几对我们自然很容易想到用哈希表。 public int subarraySum(int[] nums, int k) {if (nums.length 0) {return 0;}// key:前缀和,value:出现次数HashMapInteger,Integer map new HashMap();//细节这里需要预存前缀和为 0 的情况否则会漏掉前几位就满足的情况// 也就是会漏掉 Sjk 即 n1..nj 恰好等于 k 的情况// 因为这样的 n1..nj 虽然等于 k 但是没有 S0 给你减那么我们就默认 n00,S00// 减个 0 就不会对你的结果有任何影响了所以需要map.put(0,1),垫下底map.put(0, 1);int count 0;int presum 0;// 既然是不断确定 Sj 然后往前找有几个对应的 S(i-1)那么没必要先求出前缀和数组再遍历// 更新 presum 的过程实际上就是遍历前缀和数组确定 j 的过程for (int x : nums) {presum x;// 当前前缀和已知判断是否含有 presum - k的前缀和那么我们就知道某一区间的和为 k 了。// 比如 i 为 4当前前缀和 S4 为 n1n2n3n4 presum 如果有一个前缀和为 presum - k// 比如 S2 和为 presum - k即 n1n2 presum - k那么 S4-S2 presum - (presum - k) k // 也就是说存在区间为 n3n4 kif (map.containsKey(presum - k)) {count map.get(presum - k);//获取次数}//更新map.put(presum,map.getOrDefault(presum,0) 1);}return count;}
