数组：和为k的子数组题目解题思路代码总结

63 阅读 0 评论 42 点赞

我是靠谱客的博主负责哈密瓜，最近开发中收集的这篇文章主要介绍数组：和为k的子数组题目解题思路代码总结，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

文章目录

题目
解题思路
- 暴力枚举法
- 前缀和+哈希表优化解法
代码
总结

题目

整数组成的数组nums中，求连续子数组的和等于k的个数。

解题思路

暴力枚举法

直观的解法是，枚举整数数组nums[0…i],对nums[i]，您需要计算下标0…i之间存在多少个数组和等于k的个数。时间复杂度为O（n*n)。
代码如下

public int subarraySumNormal(int[] nums, int k) {
    int count = 0;
    //枚举nums
    int end = 0;
    int sum = 0;
    for(end =0; end < nums.length; end++) {
        sum = 0;
        for(int start = end; start >= 0; start--) { //统计0...j..i中有多少个满足sum[j] == k的个数
            sum += nums[start];
            if(sum == k) count++;
        }
    }
    return count;
}

前缀和+哈希表优化解法

从暴力枚举法中，我们可以发现可优化的地方是统计满足条件sum[j] == k的个数。如果查找sum[j]的时间时间复杂度降到为O(1)就好了。
您观察下枚举nums的过程：
输入：nums = {1,2,3}; k = 3;

i	sum（子数组之和）
0	1
1	3
2	6

sum[0] = 1;
sum[1] = sum[0] + nums[1] = 3
sum[2] = sum[1] + nums[2] = 6
可????️规律： sum[pre] + nums[i ] = sum[i]; 具体来说，枚举到数组下标为i时，sum[i]等于前面一个数i-1的和加上当前nums[i]的值。
您可以用一个哈希表,缓存枚举过的子数字和sum[pre]（我们简称其为前缀和）。

回到我们的要解决的实际问题上：在[0… pre…i]中，求连续子数组的和为k的个数。
推导可得：sum[i] = k + sum[pre]。
那么简单移动方程可得，sum[pre] = sum[i] - k。
所以最终只需要求满足条件的前缀和的个数即可。代码如下：

代码

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> mp = new HashMap<>();
        mp.put(0,1);
        int count = 0;
        int sum = 0;

        for(int num: nums) {
            sum += num;
            count += mp.getOrDefault(sum - k, 0);// 问题转化成：求前缀和（其等于sum[i] - k）的个数。                             
            mp.put(sum, mp.getOrDefault(sum, 0) + 1); //记录前缀和： pre
        }
        return count;
    }
}