523. Continuous Subarray Sum

发表于 | 分类于 | 浏览 次

Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to a multiple of k, that is, sums up to nk where n is also an *integer**.

Example 1:

1
2
3
Input: [23, 2, 4, 6, 7],  k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:

1
2
3
Input: [23, 2, 6, 4, 7],  k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

关于边界：

1
2
Input: [0, 0],  k=-1
Output: True

无论k等于何值，只要n=0，那么n*k永远都是0。因此，只要数组中所有元素的总和为0，并且数组中元素个数多于1个，那么都返回True。

1
2
3
4
5
Input: [],  k= 0
Output: False

Input: [0],  k=0
Output: False

数组中元素个数少于2个。

解法1: 二重循环枚举所有可能的子数组组合

时间复杂度分析

时间复杂度为O(n2)

解法2：使用map

使用一个字典mp来保存之前出现过的累加和，因为这里要求长度至少为2，所以这里需要计算最长长度。举个例子来说明这个问题。

1
2
Input: [5, 0, 0],  k=0
Output: False

当k=0时，后面两个0组成子数组[0,0]，这个子数组的和为0，且长度为2，所以满足条件。具体步骤为：
初始时，sum = 0, mp为mp[0] = -1。
第一次循环时，i = 0，sum = 5，因为5不在mp中，所以，往mp中添加一个元素5，mp[5] = 0。
第二次循环时，i = 1，sum = 5，5已经在mp中，但是i - mp[5] = 1 - 0 = 1 < 2，所以，当前还不满足条件。此时，不能更新累加和5出现的位置。如果此时更新了累加和5出现的位置，那么统计的将是最短子数组。
第三次循环时，i = 2，sum = 5，5已经在mp中，并且i - mp[5] = 2 - 0 = 2，所以，满足条件，返回true。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int sum = accumulate(nums.begin(), nums.end(), 0);  // temp为nums中所有元素的累加和
        if(!sum && nums.size() > 1){
            return true;
        }
        map<int, int> mp;
        mp[0] = -1;
        sum = 0;
        
        for(int i=0;i<nums.size();++i){
            sum += nums[i];
            int tmp = (k == 0) ? sum : sum % k;
            if(mp.find(tmp) != mp.end()){
                if(i - mp[tmp] > 1){
                    return true;
                }
            }else{
                mp[tmp] = i;                    
            }
        }
        return false;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

相关题目

leetcode 974

leetcode 560

leetcode 525

leetcode 581