企业网站建设ppt介绍,邵阳做网站哪个公司好,深圳找网站建设公司,天眼查公司查询企业查询官网力扣解题-560. 和为 K 的子数组
给你一个整数数组 nums 和一个整数 k #xff0c;请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1#xff1a;
输入#xff1a;nums [1,1,1], k 2
输出#xff1a;2
示例 2#xff1a;
输入…力扣解题-560. 和为 K 的子数组给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。示例 1输入nums [1,1,1], k 2输出2示例 2输入nums [1,2,3], k 3输出2提示1 nums.length 2 * 104-1000 nums[i] 1000-107 k 107第一次解答解题思路核心方法前缀和 哈希表统计频次将暴力枚举子数组的O(n²)时间复杂度优化至O(n)利用前缀和的数学性质快速定位和为k的子数组是该问题的最优解法。核心原理铺垫前缀和定义prefixSum[i]表示数组前i个元素的和prefixSum[0] 0prefixSum[1] nums[0]prefixSum[2] nums[0]nums[1]以此类推。子数组和公式对于子数组nums[start...end]从下标start到end其和 prefixSum[end1] - prefixSum[start]。问题转化要找和为k的子数组即满足prefixSum[end1] - prefixSum[start] k→prefixSum[start] prefixSum[end1] - k。因此遍历到end位置时只需统计之前出现过的prefixSum[start] (当前前缀和 - k)的次数即可得到以end为结尾的、和为k的子数组个数。具体步骤初始化关键变量prefixCountHashMapLong, Integer键为前缀和值为该前缀和出现的次数解决重复前缀和的统计问题初始化prefixCount.put(0L, 1)表示“前缀和为0”的情况出现1次对应“空前缀”即数组开始之前的虚拟前缀用于处理从下标0开始的子数组currSumlong类型的当前前缀和避免int溢出因为nums元素可正可负累加后可能超出int范围初始值为0count统计和为k的子数组总数初始值为0。遍历数组计算前缀和遍历每个元素num将num累加到currSum得到当前前缀和计算目标前缀和target currSum - k若存在该前缀和说明有子数组以当前位置结尾且和为k若prefixCount包含target则将count加上prefixCount.get(target)即符合条件的子数组个数将当前前缀和currSum存入prefixCount若已存在则次数1不存在则初始化为1prefixCount.getOrDefault(currSum, 0)1。返回结果遍历完成后count即为和为k的子数组总数直接返回。核心优化逻辑说明时间复杂度优化暴力解法需枚举所有子数组O(n²)无法适配n2×10⁴的规模前缀和哈希表仅需一次遍历O(n)哈希表的查找/插入均为O(1)整体时间复杂度为O(n)完全满足题目性能要求。数据类型选择使用long存储前缀和避免因nums元素累加如2×10⁴个1000相加导致int溢出保证计算准确性。性能表现说明耗时30ms击败25.84%的用户该解法是本题的标准最优解多数提交均采用此逻辑耗时差异主要来自评测机环境如哈希表的哈希冲突、JVM优化等内存消耗48.3MB击败23.38%的用户核心原因是哈希表存储了所有前缀和的频次空间复杂度为O(n)最坏情况下所有前缀和唯一属于合理的空间开销。执行耗时:30 ms,击败了25.84% 的Java用户内存消耗:48.3 MB,击败了23.38% 的Java用户publicintsubarraySum(int[]nums,intk){MapLong,IntegerprefixCountnewHashMap();prefixCount.put(0L,1);longcurrSum0;intcount0;for(intnum:nums){currSumcurrSumnum;longtargetcurrSum-k;if(prefixCount.containsKey(target)){countcountprefixCount.get(target);}prefixCount.put(currSum,prefixCount.getOrDefault(currSum,0)1);}returncount;}扩展1输出符合条件的子数组扩展原理在基础解法的哈希表中不再仅存储前缀和的出现次数而是存储该前缀和对应的所有索引即前缀和结束的位置。遍历过程中找到目标前缀和后通过索引还原出具体的子数组元素。具体逻辑prefixMapMapLong, ListInteger键为前缀和值为该前缀和出现的所有下标如前缀和0对应下标-1前缀和1对应下标0等初始化prefixMap.put(0L, new ArrayList(Arrays.asList(-1)))空前缀的下标为-1用于还原从0开始的子数组遍历到下标i时若找到目标前缀和target则遍历prefixMap.get(target)中的所有起始前缀下标startIndex子数组的实际起始下标为startIndex 1因为startIndex是前缀和的结束下标子数组从下一个位置开始子数组的结束下标为i遍历[startIndex1, i]的元素封装为列表加入结果每次遍历后将当前下标i加入prefixMap中对应前缀和的列表记录该前缀和的出现位置。publicListListIntegersubarraysWithSumK(int[]nums,intk){ListListIntegerresultnewArrayList();// Map前缀和, 所有对应的前缀索引即前缀和结束的位置MapLong,ListIntegerprefixMapnewHashMap();// 初始化空前缀前缀和0对应索引-1表示在数组开始之前prefixMap.put(0L,newArrayList(Arrays.asList(-1)));longcurrSum0;for(inti0;inums.length;i){currSumnums[i];longtargetcurrSum-k;// 如果存在 target说明有子数组以 i 结尾且和为 kif(prefixMap.containsKey(target)){for(intstartIndex:prefixMap.get(target)){// 子数组从 startIndex 1 到 iListIntegersubarraynewArrayList();for(intjstartIndex1;ji;j){subarray.add(nums[j]);}result.add(subarray);}}// 将当前前缀和对应的索引 i 加入 mapprefixMap.computeIfAbsent(currSum,key-newArrayList()).add(i);}returnresult;}扩展2输出符合条件的子数组的索引扩展原理与“输出子数组元素”的逻辑一致仅将“收集元素”改为“收集子数组的起始/结束下标”无需遍历元素直接通过索引计算得到子数组的区间[start, end]效率更高。具体逻辑结果列表result存储int[]每个数组包含两个元素子数组的起始下标和结束下标找到目标前缀和target后遍历其对应的起始前缀下标startPrefix子数组起始下标 startPrefix 1空前缀下标-1对应起始下标0子数组结束下标 当前遍历的下标i将new int[]{start, end}加入结果列表其余逻辑与“输出子数组”完全一致仅结果形式不同。publicListint[]subarrayIndices(int[]nums,intk){Listint[]resultnewArrayList();MapLong,ListIntegerprefixMapnewHashMap();prefixMap.put(0L,Arrays.asList(-1));longcurrSum0;for(inti0;inums.length;i){currSumnums[i];longtargetcurrSum-k;if(prefixMap.containsKey(target)){for(intstartPrefix:prefixMap.get(target)){intstartstartPrefix1;intendi;result.add(newint[]{start,end});}}prefixMap.computeIfAbsent(currSum,x-newArrayList()).add(i);}returnresult;}总结基础解法的核心是前缀和哈希表利用数学公式将子数组和问题转化为前缀和的差值问题通过哈希表统计前缀和频次将时间复杂度优化至O(n)扩展解法的核心是存储前缀和的索引在基础解法的哈希表中将“频次”改为“索引列表”通过索引还原子数组的区间或元素实现从“统计个数”到“还原具体子数组”的扩展本题的关键优化点用long存储前缀和避免溢出初始化前缀和0对应下标-1处理从数组起始位置开始的子数组哈希表的核心作用是快速查找目标前缀和避免重复计算。
