20天速通LeetCode day07：前缀和

前言今日练习目的掌握前缀和思维。前缀和的核心价值是能实现在O(1)时间求区间和是各类子数组问题的常用工具560和为k的子数组题目要求给定一个整数数组nums和整数k要求统计并返回和为k的子数组核心思路前缀和哈希表利用前缀和sum[i]表示数组前i个元素和结合哈希表优化定义sum[i]表示前i个元素和一个子数组[j1,i]的和为k等价于sum[i]−sum[j]k⇒sum[j]sum[i]−k用一个哈希表map记录前缀和出现的次数代码实现classSolution{publicintsubarraySum(int[]nums,intk){MapInteger,IntegerprefixSumnewHashMap();prefixSum.put(0,1);// 初始化前缀和 0 出现一次intcount0;intcurrSum0;for(intnum:nums){currSumnum;// 更新前缀和// 如果存在前缀和 currSum - k则说明找到一个子数组countprefixSum.getOrDefault(currSum-k,0);// 更新哈希表prefixSum.put(currSum,prefixSum.getOrDefault(currSum,0)1);}returncount;}}总结本题本质通过前缀和哈希表的方式。哈希表用来统计前缀和出现的次数本题有点像两数之和都是用哈希表快速查找差值不同点在于两数之和是找出下标本题是统计出现的次数209长度最小的子数组题目要求给定一个正整数数组nums和一个整数target要求找出长度最小的连续子数组使得子数组元素之和target。不存在则返回0核心思路前缀和二分查找用前缀和快速求区间和将问题转化为二分查找找出 最小的右边界 j使用Arrays.binarySearch 找 j代码实现classSolution{publicintminSubArrayLen(inttarget,int[]nums){intnnums.length;int[]prefixnewint[n1];//计算前缀和for(inti0;in;i){prefix[i1]prefix[i]nums[i];}intminLenInteger.MAX_VALUE;//遍历每个左边界for(inti0;in;i){intkeyprefix[i]target;//二分查找最小j使prefix[j]keyintjArrays.binarySearch(prefix,key);if(j0){// binarySearch 返回 -(插入点)-1j-j-1;}if(jn){minLenMath.min(minLen,j-i);}}returnminLenInteger.MAX_VALUE?0:minLen;}}238除了自身以外数组的乘积题目要求给定一个整数数组nums返回一个数组answer要求answer[i]nums 中除 nums[i] 之外所有元素的乘积核心思路前缀积prefix[i]表示nums[0…i-1]的乘积后缀积suffix[i]表示nums[i1…n-1]的乘积那么answer[i]prefix[i]*suffix[i]代码实现publicint[]productExceptSelf(int[]nums){intnnums.length;int[]answernewint[n];// 前缀积answer[0]1;for(inti1;in;i){answer[i]answer[i-1]*nums[i-1];}// 后缀积intR1;for(intin-1;i0;i--){answer[i]answer[i]*R;R*nums[i];}returnanswer;}总结核心技巧用前缀积记录左边乘积用后缀积记录右边乘积相乘即可得到每个位置除自身外的乘积优化空间先存前缀积在 answer用一个变量 R 代替后缀积数组