【leetcode刷题】T17-连续的子数组和
这是木又陪伴你的第27天
今天分享leetcode第17篇文章，也是leetcode第523题—连续的子数组和（Continuous Subarray Sum），地址是：https://leetcode.com/problems/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 the multiple of k, that is, sums up to n*k where n is also an integer.
Example:
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.
【中文题目】
给定一个包含非负数的数组和一个目标整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，总和为 k 的倍数，即总和为 n*k，其中 n 也是一个整数。
示例:
输入: [23,2,4,6,7], k = 6
输出: True
解释: [2,4] 是一个大小为 2 的子数组，并且和为 6。
【思路】
首先，我们可以暴力破解，得到所有的子数组和，判断有没有和是n*k
有趣的是，我们可以使用sums数组存储从第0个元素到当前元素的和，这样i->j子数组的和为sums[j]-sums[i]，时间复杂度为O(n^2)
那么时间复杂度可以降低吗？
我们能不能用hash表来代替遍历过程，即求(sums[j] - sums[i]) % k == 0，相当于对于sums[j]，在其前面找一个子数组和为sums[j] % k。当然，这里k不能为0，为0的时候需要找到元素为sums[j]
值得注意的是：k为0时需要单独处理；sums[j]也可能直接等于n*K（即从数组第0个元素到第j个元素满足条件，此时不需要减去sums[i]）
【代码】
python版本
暴力破解
class Solution(object):
def judge_divided_by_k(self, num, k):
# 特殊情况0
if k == 0:
if num == 0:
return True
else:
if num % k == 0:
return True
return False
def checkSubarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
length = len(nums)
if length < 1:
return 0
sums = [nums[0]] * length
# 统计0->i的元素之和
for i in range(1, length):
sums[i] = sums[i-1] + nums[i]
# 得到i->j元素之和，间隔至少为2
for i in range(length):
if i > 0 and self.judge_divided_by_k(sums[i], k):
return True
for j in range(i+2, length):
if self.judge_divided_by_k(sums[j] - sums[i], k):
return True
return False
hash表
class Solution(object):
def checkSubarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
length = len(nums)
if length < 1:
return 0
sums = {0:-1}
tmp = 0
# 统计0->i的元素之和
for i in range(length):
# k==0时，sums字典存入tmp；否则存入tmp%k
tmp = (tmp + nums[i])
if k != 0:
tmp = tmp % k
if tmp not in sums:
sums[tmp] = i
elif i - sums[tmp] > 1:
return True
return False
C++版本
暴力破解
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
vector<int> sums;
if(nums.size() < 2)
return false;
sums.push_back(nums[0]);
// 统计0->i的元素之和
for(int i=1; i < nums.size(); i++){
sums.push_back(sums[i-1] + nums[i]);
}
// 得到i->j元素之和，间隔至少为2
for(int i=0; i < sums.size(); i++){
if(i > 0){
// 特殊情况k=0
if(k == 0){
if(sums[i] == 0)
return true;
}else{
if(sums[i] % k == 0)
return true;
}
}
for(int j=i+2; j < sums.size(); j++){
int num = sums[j] - sums[i];
if(k == 0){
if(num == 0)
return true;
}else{
if(num % k == 0)
return true;
}
}
}
return false;
}
};
hash表
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
map<int, int> sums;
sums[0] = -1;
int tmp = 0;
for(int i=0; i < nums.size(); i++){
// k==0时，sums字典存入tmp；否则存入tmp%k
tmp += nums[i];
if(k != 0)
tmp = tmp % k;
if(sums.find(tmp) == sums.end())
sums[tmp] = i;
else
if(i - sums[tmp] > 1)
return true;
}
return false;
}
};
相关文章：
T15-最大子数组和
T16-乘积最大子序列
思考：如果需要返回满足条件的子数组的个数，应该怎么处理？
给我好看