企业官网建设流程全解析

在阿里云服务器做淘客网站,wordpress需要php,免费ai图片生成器,个人工作室网站模板930. 和相同的二元子数组 问题描述 给你一个二元数组 nums 和一个整数 goal#xff0c;请你统计并返回有多少个非空连续子数组的和等于 goal。 示例#xff1a; 输入: nums [1,0,1,0,1], goal 2 输出: 4 解释: 有4个满足要求的子数组: [1,0,1], [1,0,1,0], [0,1,0,1], [1,0…930. 和相同的二元子数组问题描述给你一个二元数组nums和一个整数goal请你统计并返回有多少个非空连续子数组的和等于goal。示例输入: nums [1,0,1,0,1], goal 2 输出: 4 解释: 有4个满足要求的子数组: [1,0,1], [1,0,1,0], [0,1,0,1], [1,0,1] 输入: nums [0,0,0,0,0], goal 0 输出: 15 解释: 所有子数组的和都是0总共有15个非空子数组。算法思路前缀和 哈希表计算前缀和数组其中prefixSum[i]表示nums[0...i-1]的和对于每个位置i需要找到有多少个位置j i满足prefixSum[i] - prefixSum[j] goal即prefixSum[j] prefixSum[i] - goal使用哈希表记录每个前缀和出现的次数可以在O(1)时间内查询滑动窗口goal 0由于数组只包含0和1子数组和具有单调性可以使用滑动窗口计算和小于等于goal的子数组数量结果 和小于等于goal的数量 - 和小于等于goal-1的数量暴力枚举所有可能的子数组计算每个子数组的和统计和等于goal的数量代码实现方法一前缀和 哈希表classSolution{/** * 使用前缀和 哈希表统计和为goal的子数组数量 * * param nums 二元数组只包含0和1 * param goal 目标和 * return 和为goal的非空连续子数组数量 */publicintnumSubarraysWithSum(int[]nums,intgoal){// 哈希表存储前缀和及其出现次数MapInteger,IntegerprefixCountnewHashMap();// 初始化前缀和为0出现1次空数组prefixCount.put(0,1);intcurrentSum0;// 当前前缀和intresult0;// 结果计数for(intnum:nums){currentSumnum;// 查找是否存在前缀和 currentSum - goalinttargetcurrentSum-goal;if(prefixCount.containsKey(target)){resultprefixCount.get(target);}// 更新当前前缀和的计数prefixCount.put(currentSum,prefixCount.getOrDefault(currentSum,0)1);}returnresult;}}方法二滑动窗口classSolution{/** * 使用滑动窗口 * * param nums 二元数组 * param goal 目标和 * return 和为goal的子数组数量 */publicintnumSubarraysWithSum(int[]nums,intgoal){if(goal0){// 特殊处理goal0的情况returncountZeroSubarrays(nums);}// 计算和 goal 的子数组数量intatMostGoalcountSubarraysAtMost(nums,goal);// 计算和 goal-1 的子数组数量intatMostGoalMinusOnecountSubarraysAtMost(nums,goal-1);// 和恰好等于goal的数量 atMostGoal - atMostGoalMinusOnereturnatMostGoal-atMostGoalMinusOne;}/** * 计算和小于等于target的子数组数量 */privateintcountSubarraysAtMost(int[]nums,inttarget){if(target0)return0;intleft0;intcurrentSum0;intcount0;for(intright0;rightnums.length;right){currentSumnums[right];// 收缩窗口直到和 targetwhile(currentSumtarget){currentSum-nums[left];left;}// 以right结尾的满足条件的子数组数量 right - left 1countright-left1;}returncount;}/** * 专门处理goal0的情况统计连续0的子数组数量 */privateintcountZeroSubarrays(int[]nums){intcount0;intconsecutiveZeros0;for(intnum:nums){if(num0){consecutiveZeros;countconsecutiveZeros;// 连续k个0可以形成k*(k1)/2个子数组}else{consecutiveZeros0;}}returncount;}}方法三暴力classSolution{/** * 暴力枚举所有子数组 */publicintnumSubarraysWithSum(int[]nums,intgoal){intcount0;intnnums.length;for(inti0;in;i){intsum0;for(intji;jn;j){sumnums[j];if(sumgoal){count;}elseif(sumgoal){// 由于数组只包含0和1后续和只会更大break;}}}returncount;}}算法分析方法时间复杂度空间复杂度前缀和哈希表O(n)O(n)滑动窗口O(n)O(1)暴力O(n²)O(1)算法过程输入nums [1,0,1,0,1], goal 2方法一初始化prefixCount {0:1},currentSum 0,result 0num1:currentSum1,target1-2-1不存在,prefixCount{0:1,1:1}num0:currentSum1,target1-2-1不存在,prefixCount{0:1,1:2}num1:currentSum2,target2-20存在计数1,result1,prefixCount{0:1,1:2,2:1}num0:currentSum2,target2-20存在计数1,result2,prefixCount{0:1,1:2,2:2}num1:currentSum3,target3-21存在计数2,result4,prefixCount{0:1,1:2,2:2,3:1}返回4测试用例publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 测试用例1标准示例int[]nums1{1,0,1,0,1};System.out.println(Test 1: solution.numSubarraysWithSum(nums1,2));// 4// 测试用例2全0数组int[]nums2{0,0,0,0,0};System.out.println(Test 2: solution.numSubarraysWithSum(nums2,0));// 15// 测试用例3全1数组int[]nums3{1,1,1,1,1};System.out.println(Test 3: solution.numSubarraysWithSum(nums3,3));// 3// 测试用例4单元素int[]nums4{1};System.out.println(Test 4: solution.numSubarraysWithSum(nums4,1));// 1System.out.println(Test 4: solution.numSubarraysWithSum(nums4,0));// 0// 测试用例5goal大于总和int[]nums5{1,0,1};System.out.println(Test 5: solution.numSubarraysWithSum(nums5,5));// 0// 测试用例6goal为0混合数组int[]nums6{1,0,0,1,0};System.out.println(Test 6: solution.numSubarraysWithSum(nums6,0));// 4// 连续0的子数组[0], [0], [0,0], [0] → 4个// 测试用例7goal为负数int[]nums7{1,0,1};System.out.println(Test 7: solution.numSubarraysWithSum(nums7,-1));// 0// 测试用例8大数组int[]nums8newint[1000];Arrays.fill(nums8,1);System.out.println(Test 8: solution.numSubarraysWithSum(nums8,500));// 501// 测试用例9交替数组int[]nums9{1,0,1,0,1,0};System.out.println(Test 9: solution.numSubarraysWithSum(nums9,2));// 6// 测试用例10边界情况int[]nums10{0};System.out.println(Test 10: solution.numSubarraysWithSum(nums10,0));// 1}关键点前缀和子数组和 prefixSum[j] - prefixSum[i]转化为查找问题对于每个j找有多少个i满足条件滑动窗口数组元素非负这里是0和1利用单调性窗口扩大时和增加窗口缩小时和减少哈希表初始化必须初始化prefixCount.put(0, 1)对应空数组的前缀和处理从索引0开始的子数组常见问题为什么前缀和要初始化prefixCount[0] 1当子数组从索引0开始时需要prefixSum[j] - prefixSum[-1] goal而prefixSum[-1]定义为0所以需要记录前缀和0的出现次数滑动窗口数组元素非负所以子数组和具有单调性