【算法挨揍日记】day15——560. 和为 K 的子数组、974. 和可被 K 整除的子数组

素颜马尾好姑娘i 2024-03-01 08:25 64阅读 0赞

![57e8b06125294c68bea947751a5149e0.png][]

## 560. 和为 K 的子数组 ##

[560. 和为 K 的子数组][560. _ K]

### 题目描述： ###

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

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

### ![7a37af5dd55e489a80774acec4598af5.png][] ###

### 解题思路： ###

> 我们可以很容易想到暴力解法，但是时间复杂度为N^2，我们可以是用前缀和对其优化
> 
> 我们可以利用前缀和数组sum来记录，sum【i】代表到i位置的子数组之和
> 
> ![fb56d4778ed24e6eb260ceb652979877.png][]
> 
> 假设这是0-i的数组后面的我们先不看，我们可以将其分成两部分，一部分之和为k，另外一部分为sum【i】-k，本题是求和为k的数组的个数
> 
> 那问题就可以变为在sum【i】-k中有多少个子数组等于sum【i】-k
> 
> 这段区间正负都有，子区间可能不只有一个噢！！！
> 
> 我们可以利用hash来完成本题，一个参数为前缀和，一个参数为次数 ，都是int类型
> 
> 我们可以利用一个int变量来代替sum数组，因为sum不用每个都记录下来，只要记录上一个位置

### 解题代码： ###

class Solution {
    public:
        int subarraySum(vector<int>& nums, int k) {
            unordered_map<int,int>hash;
            hash[0]=1;
            int ret=0;
            int sum=0;
            for(auto x:nums)
            {
                sum+=x;
                if(hash.count(sum-k))ret+=hash[sum-k];
                hash[sum]++;
            }
            return ret;
        }
    };

--------------------

## 974. 和可被 K 整除的子数组 ##

[974. 和可被 K 整除的子数组][974. _ K]

### 题目描述： ###

给定一个整数数组 `nums` 和一个整数 `k` ，返回其中元素之和可被 `k` 整除的（连续、非空） **子数组** 的数目。

**子数组** 是数组的 **连续** 部分。

### ![193a375800d943cbbd5e3324a89e0c25.png][] ###

### 解题思路： ###

> 解决本题我们先来补充两个知识点
> 
>  *  同余定理：（a-b）/p=k....0可以转换为a%p=b%p，具体证明可见[同余定理\_百度百科 (baidu.com)][_baidu.com]
>  *  C++中，负数（a）%正数（p），在C++负数求余正数正确应该为正数，但是计算结果为负数，我们对其修正时期变成a%p+p，但是为了考虑到正负统一的问题，我们再次进行修正让其变为（a%p+p）%p
> 
> 接下来我们来看一下本题，本题如果你做了上一题，你会发现基本上是类似的
> 
> 只不过判断条件不太一样罢了
> 
> ![d738c6d364b94574ae8b47758a225a43.png][]
> 
> 题目要求的可以被k整除的数组为图中sum-x部分，那就变成（sum-x）%k==0也就变成了sum%k==x%k，也就转为为在【0，i-1】这个区间内有多少个前缀和的余数等于sum%k

### 解题代码： ###

class Solution {
    public:
        int subarraysDivByK(vector<int>& nums, int k) {
            unordered_map<int,int>hash;
            hash[0%k]=1;
            int ret=0;
            int sum=0;
            for(auto x:nums)
            {
                sum+=x;
                int r=(sum%k+k)%k;
                if(hash.count(r))ret+=hash[r];
                hash[r]++;
            }
            return ret;
        }
    };

![56d5f6813ccd4fdc8f4376804f80b5f3.gif][]

[57e8b06125294c68bea947751a5149e0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/5d9518d741a241f48ecb92fecb96bf61.png
[560. _ K]: https://leetcode.cn/problems/subarray-sum-equals-k/
[7a37af5dd55e489a80774acec4598af5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/4429de695c8645c59dbe3fb7b9b0a1eb.png
[fb56d4778ed24e6eb260ceb652979877.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/eaa87e10f42f43c6ad95e4628ae0b519.png
[974. _ K]: https://leetcode.cn/problems/subarray-sums-divisible-by-k/
[193a375800d943cbbd5e3324a89e0c25.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/4d8954f5275345de89bb5e0d4ce4e13e.png
[_baidu.com]: https://baike.baidu.com/item/%E5%90%8C%E4%BD%99%E5%AE%9A%E7%90%86/1212360
[d738c6d364b94574ae8b47758a225a43.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/ba02d974883b47c0bcfc8d50eae93368.png
[56d5f6813ccd4fdc8f4376804f80b5f3.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/fac44064dbf545d3a72cb234612f056e.png