网站建设一般怎么付款,seo排名软件哪个好,网站底部备案信息,网站建设+人员+年终总结这道题我用的是暴力法#xff0c;当然也是不断的提交不断发现问题改出来的#xff0c;比如我之前是算到和大于目标值就break#xff0c;其实不行因为后面还可以有负数#xff0c;我把break删了。后面和为目标之后就答案1然后break然后下一次遍历#xff0c;测试用例中就出… 这道题我用的是暴力法当然也是不断的提交不断发现问题改出来的比如我之前是算到和大于目标值就break其实不行因为后面还可以有负数我把break删了。后面和为目标之后就答案1然后break然后下一次遍历测试用例中就出现了合理的子串后面还有一个0于是我改成直到遍历完最后一个才结束循环所以我把两个break都删了我以为会超时没想到还是过了以下是我的代码
class Solution {public int subarraySum(int[] nums, int k) {int ans 0;int n nums.length;int sum0;for(int i0;in;i){sum 0;for(int ji;jn;j){sumnums[j];if(sum k){ans;}}}return ans;}
}
就是最简单的暴力法用ij两个指针作为子串的起点和终点然后把子串的所有数的和加起来如何等于kans。这里就需要注意我前面提到的无论sumk还是sumk都不能break要遍历到最后一个数自动结束外层循环每次sum归0。
题解的方法一和我的是一样的暴力枚举方法二是用HashMap来存前缀和key是前缀和value值这个前缀和出现的次数pre[i]表示前i个数的和pre[j-1]表示前j-1个数的和当pre[i]-pre[j-1]k时我们就找到了这个子串的起始位置j所以我们只需要一遍遍历即可算出pre[i]放入hashmap如果有这个key就value1同时我们看hashmap中有没有pre[i]-k这个key如果有答案就加上这个key的value以下时哈希优化的代码
public class Solution {public int subarraySum(int[] nums, int k) {int count 0, pre 0;HashMap Integer, Integer mp new HashMap ();mp.put(0, 1);for (int i 0; i nums.length; i) {pre nums[i];if (mp.containsKey(pre - k)) {count mp.get(pre - k);}mp.put(pre, mp.getOrDefault(pre, 0) 1);}return count;}
}
