怎样做网贷网站,深圳龙岗区律师,怎么查看一个网站是不是伪静态,无忧中英繁企业网站系统 完整【问题描述】[第560题][和为K的子数组][中等]
给定一个整数数组和一个整数 k#xff0c;你需要找到该数组中和为 k 的连续的子数组的个数。示例 1 :输入:nums [1,1,1], k 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :数组的长度为 [1, 20,000]。
数组中元素的范围…【问题描述】[第560题][和为K的子数组][中等]
给定一个整数数组和一个整数 k你需要找到该数组中和为 k 的连续的子数组的个数。示例 1 :输入:nums [1,1,1], k 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] 且整数 k 的范围是 [-1e7, 1e7]。
【解答思路】
1. 暴力
时间复杂度O(N^2) 空间复杂度O(1) public int subarraySum(int[] nums, int k) {int count 0;int len nums.length;for (int left 0; left len; left) {int sum 0;// 区间里可能会有一些互相抵销的元素for (int right left; right len; right) {sum nums[right];if (sum k) {count;}}}return count;}
2.前缀和
构建前缀和数组以快速计算区间和注意在计算区间和的时候下标有偏移。 时间复杂度O(N^2) 空间复杂度O(N)
public class Solution {public int subarraySum(int[] nums, int k) {int len nums.length;// 计算前缀和数组int[] preSum new int[len 1];preSum[0] 0;for (int i 0; i len; i) {preSum[i 1] preSum[i] nums[i];}int count 0;for (int left 0; left len; left) {for (int right left; right len; right) {// 区间和 [left..right]注意下标偏移if (preSum[right 1] - preSum[left] k) {count;}}}return count;}
}
3. 前缀和 哈希表优化
时间复杂度O(N) 空间复杂度O(1) 由于只关心次数不关心具体的解我们可以使用哈希表加速运算 由于保存了之前相同前缀和的个数计算区间总数的时候不是一个一个地加时间复杂度降到了 O(N)O(N)。 preSumFreq.put(0, 1)数组中有些数直接就等于k
import java.util.HashMap;
import java.util.Map;public class Solution {public int subarraySum(int[] nums, int k) {// key前缀和valuekey 对应的前缀和的个数MapInteger, Integer preSumFreq new HashMap();// 对于下标为 0 的元素前缀和为 0个数为 1preSumFreq.put(0, 1);int preSum 0;int count 0;for (int num : nums) {preSum num;// 先获得前缀和为 preSum - k 的个数加到计数变量里if (preSumFreq.containsKey(preSum - k)) {count preSumFreq.get(preSum - k);}// 然后维护 preSumFreq 的定义preSumFreq.put(preSum, preSumFreq.getOrDefault(preSum, 0) 1);
//getOrDefault 有就是get preSum的对应的值 不存在就为0}return count;}
}
public class Solution {public int subarraySum(int[] nums, int k) {// 记录区间和为 k 的个数和数组前缀元素和。int ans 0, curr 0;// 创建 hashMap 记录数组前缀和以及当前和对应的前缀个数。HashMapInteger, Integer map new HashMap();// 遍历前初始化前缀和为 0 的个数为 1 。map.put(0, 1);for (int num : nums) {// 依次遍历并累加数组元素。curr num;int pre curr - k;// 如果之前有前缀和等于 curr - k 表示从该前缀之后到当前元素区间和为 k 。if (map.containsKey(pre)) {// 叠加和为 k 的区间个数。ans map.get(pre);}// 遍历完每个元素后记录当前前缀和以及个数。if (map.containsKey(curr)) {map.put(curr, map.get(curr) 1);} else {map.put(curr, 1);}}return ans;}
}
【总结】
1. 暴力优化
2.哈希表 关于次数的优化
3.HashMap
1 插入键值对数据 public V put(K key, V value) 2根据键值获取键值对值数据 public V get(Object key) 3获取Map中键值对的个数 public int size() 4判断Map集合中是否包含键为key的键值对 public boolean containsKey(Object key) 5判断Map集合中是否包含值为value的键值对 boolean containsValue(Object value) 6判断Map集合中是否没有任何键值对 public boolean isEmpty() 7清空Map集合中所有的键值对 public void clear() 8根据键值删除Map中键值对 public V remove(Object key)
遍历hashMap
for (Integer key : map.keySet()) { if (map.get(key) 1) {return key;}原文链接https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/bao-li-jie-fa-qian-zhui-he-qian-zhui-he-you-hua-ja/ 参考链接https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/560ti-he-wei-kde-zi-shu-zu-by-iceblood/
