Leetcode 560:和为k的子数组

Leetcode 算法

Leetcode

发布日期: 2023-08-25

更新日期: 2023-09-03

文章字数: 1.5k

阅读时长: 6 分

阅读次数:

Leetcode-560：和为k的子数组

1. 题目说明

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

示例 1 :

输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

2. 解答分析（含复杂度）

题目本质上是可以利用暴力解决的，也就是用双重循环进行和为k的子数组的个数统计即可，但是这里我们想利用更多的方法，主要分为3部分：
1. 暴力
2. 前缀和
3. 前缀和+HashMap

① 暴力解法

直接上代码：

class Solution {
    public int subarraySum(int[] nums, int k) {
         int len = nums.length;
         int sum = 0;
         int count = 0;
         //双重循环
         for (int i = 0; i < len; ++i) {
             for (int j = i; j < len; ++j) {
                 sum += nums[j];
                 //发现符合条件的区间
                 if (sum == k) {
                     count++;
                 }
             }
             //记得归零，重新遍历
             sum = 0;
         }
         return count;
    }
}

复杂度分析：
- 时间复杂度： $O(N^2)$ ，这里 $N $是数组的长度；
- 空间复杂度： $O(1)$ 。

② 前缀和

前缀和pre[i]的关键是找到前一个和后一个的关系，这里的连续子数组的元素之和恰好满足前缀求和的关系，所以可以采取。
需要注意的是：
1. 注意偏移，因为我们的nums[2]到nums[4]等于pre[5]-pre[2]，所以这样就可以得到nums[i,j]区间内的和
2. 前缀和是从pre[1]开始填充的
上代码：

class Solution {
    public int subarraySum(int[] nums, int k) {
        //前缀和数组
        int[] presum = new int[nums.length+1];
        for (int i = 0; i < nums.length; i++) {
            pre[i+1] = nums[i] + pre[i];
        }
        //统计个数
        int count = 0;
        for (int i = 0; i < nums.length; ++i) {
            for (int j = i; j < nums.length; ++j) {
              
                if (pre[j+1] - pre[i] == k) {
                    count++;
                }
            }
        }
        return count;
    }
}

复杂度分析：
- 时间复杂度： $O(N^2)$ ，这里 N 是数组的长度；
- 空间复杂度： $O(N)$ 。

③ 前缀和 + HashMap

分析上述的前缀和方法不难看出：该代码虽然用到了前缀和数组，但是对比暴力法并没有提升性能，时间复杂度仍为 $O(n^2)$ ，空间复杂度成了 $O(n)$ 。
在两数之和的题目中，我们可以看出利用HashMap进行的遍历求解，只用遍历循环数组一次即可，这里我们同样采用的做法是，我们将数组的值和索引存入map中，当我们遍历到某一值 x 时，判断 map 中是否含有 target - x即可。

代码如下：

class Solution {
    public int[] twoSum(int[] nums, int target) {

        HashMap<Integer,Integer> map  = new HashMap<>();
        //一次遍历
        for (int i = 0; i < nums.length; ++i) {
            //存在时，我们用数组得值为 key，索引为 value
            if (map.containsKey(target - nums[i])){              
               return new int[]{i,map.get(target-nums[i])};
            }
            //存入值
            map.put(nums[i],i);
        }
        //返回
        return new int[]{};
    }
}

我们完全可以通过 presum - k的个数获得 k 的个数,如图所示:

本题的代码如下：

class Solution {
    public int subarraySum(int[] nums, int k) {
        if (nums.length == 0) {
            return 0;
        }
        HashMap<Integer,Integer> map = new HashMap<>();
        //细节，这里需要预存前缀和为 0 的情况，会漏掉前几位就满足的情况
        //例如输入[1,1,0]，k = 2 如果没有这行代码，则会返回0,漏掉了1+1=2，和1+1+0=2的情况
        //输入：[3,1,1,0] k = 2时则不会漏掉
        //因为presum[3] - presum[0]表示前面 3 位的和，所以需要map.put(0,1),垫下底
        map.put(0, 1);
        int count = 0;
        int presum = 0;
        for (int x : nums) {
            presum += x;
            //当前前缀和已知，判断是否含有 presum - k的前缀和，那么我们就知道某一区间的和为 k 了。
            if (map.containsKey(presum - k)) {
                count += map.get(presum - k);//获取次数
            }
            //更新
            map.put(presum,map.getOrDefault(presum,0) + 1);
        }
        return count;
    }
}

//或者是：
class Solution {
    public int subarraySum(int[] nums, int k) {
        /*
        前缀和+HashMap(两数之和进阶版)
        若存在i与j满足sum[i,j]=sum[j+1]-sum[i]=k，对于j+1，满足条件的i的个数可以先统计出来
        前面符合条件的数据为:sum[i]=sum[j+1]-k，这里注意是i<=j，因此需要先统计了前面的再更新当前的
        与两数之和是差不多的思路，不过这个多了个前缀和
        时间复杂度:O(N) 空间复杂度:O(N)
         */
        int res = 0;
        // 前缀和还可以进一步空间优化
        int sum = 0;
        // 哈希表存储前缀和数组中缺少了某个数的个数
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);  // 初始前缀和
        for (int num : nums) {
            sum += num;
            // 先统计
            res += map.getOrDefault(sum - k, 0);
            // 再更新当前的
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return res;
    }
}

复杂度分析：
- 时间复杂度： $O(N)$ ，这里 $N$ 是数组的长度；
- 空间复杂度： $O(N)$ 。

3. 变式题目

1248. 统计「优美子数组」

给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。

请返回这个数组中 「优美子数组」 的数目。

示例 1：
输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。

分析解答：类似，只是在遇到奇数的时候将prenum更新而已。类似于HashMap,这里用数组的索引来表示哈希表中的key，对应的值模拟哈希表中的value.代码如下：

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int len=nums.length;
        int []map=new int[len+1];
        map[0]=1;
        int oddnum=0;
        int count=0;
        for(int i=0;i<len;i++){
            if(nums[i]%2!=0){//如果是奇数的话，存入oddnum
                oddnum++;
            }
            if(oddnum>=k){
                count+=map[oddnum-k];
            }
            map[oddnum]++;
        }
        return count;
    }
}