汕头网站设计价格_app开发公司怎么选_网络推广的方法有_搜索引擎推广试题

题目

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例

示例1

输入：nums = [1,1,1], k = 2
输出：2

示例2

输入：nums = [1,2,3], k = 3
输出：2

解题思路

前缀和

我们假设nums=[1,2,2,3,4,4,4],如果要求和为k的子数组个数，暴力穷举的办法，就是两层for循环遍历数组，穷举每种情况，但是要计算子数组和，在双层循环里面，我们还要再套一层循环来计算子数组和。
如下：

//外层循环，i指向左指针
for(int i=0;i<nums.length;i++){//内层循环，j指向右指针for(int j=i;j<nums.length;j++){//计算i到j的和for(int k=i;k<=j;k++){sum+=nums[k];}}
}

可以看出来，这种方式的时间复杂度达到了O($n^3$),
显然这种方法不可以。
我们引入前缀和的思想，还是nums=[1,2,2,3,4,4,4],我们要求下标2到下标4这个区间的子数组元素和，即[2,3,4]的元素和。我们可以用[1,2,2,3,4]的元素和减去[1,2]的元素和，即[2,3,4]的元素和。
我们再详细说明一下前缀和的思想。

• 初始化设置前缀和数组sum[0]=0,
• sum[1]=sum[0]+nums[0]=0+1=1,代表下标0到下标0的子数组元素和为1
• sum[2]=sum[1]+nums[1]=1+2=3,代表下标0到下标1的子数组元素和为3
• sum[3]=sum[2]+nums[2]=3+2=5代表下标0到下标2的子数组元素和为5
• sum[4]=sum[3]+nums[3]=5+3=8代表下标0到下标3的子数组元素和为8
• sum[5]=sum[4]+nums[4]=8+4=12代表下标0到下标4的子数组元素和为12
• sum={1,3,5,8,12,16,20}
• 我们算要求下标2到下标4这个区间的子数组元素和，即[2,3,4]的元素和,则可以用sum[5]-sum[2]=12-3=9。
• 可得一般性结论，我们对于下标i到下标j的子数组{nums[i]...nums[j]}的子数组和=sum[j+1]-sum[i]，表示下标0到下标j的子数组和 - 下标0到下标i-1的子数组和。

实现设计

• res表示符合条件的子数组个数
• sum是前缀和数组
• 初始化sum[0]=0
• 循环遍历数组得到前缀和数组
• 用双层循环去遍历所有子数组，在双层循环中，利用前缀和计算子数组和，如果子数组和=k，res+1;

详细代码

class Solution {public int subarraySum(int[] nums, int k) {//[1,2,2,3,4,4,4]//[1,3,5,8,12,16,20]//res表示符合条件的子数组个数int res =0;//sum是前缀和数组int[] sum = new int[nums.length+1];//初始化sum[0]=0sum[0]=0;int m=1;//循环遍历数组得到前缀和数组for(int i=0;i<nums.length;i++){sum[m]=sum[m-1]+nums[i];m++;}//用双层循环去遍历所有子数组，在双层循环中，利用前缀和计算子数组和，如果子数组和=k，res+1;for(int i=0;i<sum.length-1;i++){for(int j=i+1;j<sum.length;j++){if(sum[j]-sum[i]==k){res++;}}}return res;}
}