【LeetCode热题100】【子串】和为 K 的子数组

发布时间:2024年01月17日

题目

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

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

示例 1:

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

示例 2:

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

提示:

  • 1 <= nums.length <= 2 * 104
  • -1000 <= nums[i] <= 1000
  • -107 <= k <= 107

暴力?

直接两层循环找出所有连续子数组的和,这个时间复杂度为n2

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int answer=0;
        for(int i=0;i<nums.size();i++){
            int sum=0;
            for(int j=i;j<nums.size();j++){
                sum+=nums[j];
                if(sum==k){
                    answer++;
                }
            }
        }
        return answer;
    }
};

但是这个会超时

前缀和

考虑到存在重复对连续子数组求和,可以使用前缀和优化这个连续子数组求和,如数组1 2 3 4 5,那么前缀和就是1 3 6 10 15,任何连续子数组的和就是对应的前缀和之差,这样就可以减少求和的重复计算,实际计算时需要在前缀和数组前补个0方便做差

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int answer=0,prefix[nums.size()+1];
        prefix[0]=0;
        for(int i=0;i<nums.size();i++){
            prefix[i+1]=prefix[i]+nums[i];
        }
        for(int i=0;i<nums.size();i++){
            for(int j=i;j<nums.size();j++){
                if(prefix[j+1]-prefix[i]==k){
                    answer++;
                }
            }
        }
        return answer;
    }
};

但是还是超时

哈希优化?

其实这时候就可以想到之前做过的【LeetCode热题100】【哈希】两数之和 C++-CSDN博客

可以用哈希来优化在数组中查找和为目标值target?的两个整数的索引,因为哈希查找的时间复杂度是O(1)的

这里同样可以使用哈希查找来优化,我们的目的是想找出两个前缀和之差为k的,考虑到同一个前缀和可能存在出现多次的情况,例如 1 -1 0,k=0,这个前缀和为0的就会出现两次,因此哈希表设计key为前缀和,value为出现的次数

遍历数组元素,计算前缀和,哈希查找前缀和 - k的key是否存在,存在则说明找到了符合的前缀和,然后加上这个前缀和出现的次数

class Solution {
public:
    int subarraySum(vector<int> &nums, int k) {
        int answer = 0, prefix=0;
        unordered_map<int,int>hashMap;
        hashMap[0]=1;
        for(int x:nums){
            prefix+=x;
            if(hashMap.find(prefix-k)!=hashMap.end())
                answer+=hashMap[prefix-k];
            hashMap[prefix]++;
        }
        return answer;
    }
};

文章来源:https://blog.csdn.net/weixin_62264287/article/details/135659162
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。