算法（数组）-----和为k的子数组

和为k的子数组

题目描述：

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

解法1：暴力法，时间复杂度为O（n^2）

双循环，求出所有子数组的和，记录等于k的次数

解法2：哈希表，时间复杂度O(n)

首先思考暴力法的计算过程，我们会发现暴力法中存在很多重复计算的过程。例如我们计算数组nums[0]+nums[1]+nums[2]时，nums[1]+nums[2]被算了一次，当第二次循环计算nums[1]+nums[2]的时候，它又被计算了一次。所以，如果想要减少算法的时间复杂度，我们需要考虑如何减少重复计算。

第一步：首先我们转换一下计算思路。我们创建一个数组sum[i]，该数组代表从0位置到i位置的所有元素的累加和。于是，数组nums[]的任意一个子数组的和可以转换成  子数组的和=sum[j]-sum[i]（j>i）。

例如：我想计算nums[1]+nums[2]，那么nums[1]+nums[2]=sum[2]-sum[0];

到了这里我们就把子树的和转换成了两个累加和之间的差。这两个累加和都是从0开始累加的。

第二步：有了上面的公式，我们就需要考虑它在本题中有何作用。因为我们要找和为k的子数组。那么，也就是找sum[j]-sum[i]=k。即sum[j]-k=sum[i]。也就是说，只要存在[0,j]的累加和减去k等于另一个[0,i]的累加和，那么就一定存在累加和为k的组数组。

第三步：因为数组的个数有限，所以计算出所有的累加和时间为O(n),我们用一个HashMap记录sum[],其中key为sum[i]，value为sum[i]出现的次数。若存在sum[j]-k=sum[i]，sum[i]对应的value值为x，则代表这种情况下有x个子数组和为k。依次累加x1、x2...最终求出总个数。

代码：

public static  int subarraySum(int[] nums, int k) {
        if(nums.length==0||nums==null){
            return 0;
        }
        HashMap<Integer,Integer> hashMap=new HashMap<Integer, Integer>();
        hashMap.put(0, 1);
        int count=0;
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];        
            if(hashMap.containsKey(sum-k)){
                count+=hashMap.get(sum-k);
            }        
            hashMap.put(sum, hashMap.getOrDefault(sum, 0)+1);
        }        
        return count;
        
    }

最后

以上就是刻苦楼房为你收集整理的算法（数组）-----和为k的子数组的全部内容，希望文章能够帮你解决算法（数组）-----和为k的子数组所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。