class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k) {
}
};
974. 和可被 K 整除的子数组
给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的（连续、非空） 子数组 的数目。
子数组 是数组的 连续 部分。
示例 1：
输入：nums = [4,5,0,-2,-3,1], k = 5 输出：7 解释： 有 7 个子数组满足其元素之和可被 k = 5 整除： [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
示例 2:
输入: nums = [5], k = 9 输出: 0
提示:
1 <= nums.length <= 3 * 104-104 <= nums[i] <= 1042 <= k <= 104相似题目
原站题解
java 解法, 执行用时: 2 ms, 内存消耗: 44.9 MB, 提交时间: 2023-06-01 10:11:31
class Solution {
public int subarraysDivByK(int[] A, int K) {
int N = A.length, sum = 0, ans = 0;
int[] map = new int[K];
map[0] = 1;
for (int i = 1; i <= N; i++) {
sum = sum + A[i-1];
int key = (sum % K + K) % K;
ans += map[key];
map[key]++;
}
return ans;
}
}
golang 解法, 执行用时: 36 ms, 内存消耗: 6.6 MB, 提交时间: 2023-06-01 10:11:00
func subarraysDivByK(nums []int, k int) int {
record := map[int]int{0: 1}
sum, ans := 0, 0
for _, elem := range nums {
sum += elem
modulus := (sum % k + k) % k
record[modulus]++
}
for _, cx := range record {
ans += cx * (cx - 1) / 2
}
return ans
}
python3 解法, 执行用时: 96 ms, 内存消耗: 19.6 MB, 提交时间: 2023-06-01 10:10:46
class Solution:
def subarraysDivByK(self, nums: List[int], k: int) -> int:
record = {0: 1}
total = 0
for elem in nums:
total += elem
modulus = total % k
record[modulus] = record.get(modulus, 0) + 1
ans = 0
for x, cx in record.items():
ans += cx * (cx - 1) // 2
return ans
java 解法, 执行用时: 16 ms, 内存消耗: 48.4 MB, 提交时间: 2023-06-01 10:10:35
// 哈希表 + 单次统计
class Solution {
public int subarraysDivByK(int[] nums, int k) {
Map<Integer, Integer> record = new HashMap<Integer, Integer>();
record.put(0, 1);
int sum = 0;
for (int elem : nums) {
sum += elem;
// 注意 Java 取模的特殊性，当被除数为负数时取模结果为负数，需要纠正
int modulus = (sum % k + k) % k;
record.put(modulus, record.getOrDefault(modulus, 0) + 1);
}
int ans = 0;
for (Map.Entry<Integer, Integer> entry: record.entrySet()) {
ans += entry.getValue() * (entry.getValue() - 1) / 2;
}
return ans;
}
}
java 解法, 执行用时: 17 ms, 内存消耗: 47.9 MB, 提交时间: 2023-06-01 10:10:03
class Solution {
public int subarraysDivByK(int[] nums, int k) {
Map<Integer, Integer> record = new HashMap<Integer, Integer>();
record.put(0, 1);
int sum = 0, ans = 0;
for (int elem : nums) {
sum += elem;
// 注意 Java 取模的特殊性，当被除数为负数时取模结果为负数，需要纠正
int modulus = (sum % k + k) % k;
int same = record.getOrDefault(modulus, 0);
ans += same;
record.put(modulus, same + 1);
}
return ans;
}
}
golang 解法, 执行用时: 36 ms, 内存消耗: 6.6 MB, 提交时间: 2023-06-01 10:09:43
func subarraysDivByK(nums []int, k int) int {
record := map[int]int{0: 1}
sum, ans := 0, 0
for _, elem := range nums {
sum += elem
modulus := (sum % k + k) % k
ans += record[modulus]
record[modulus]++
}
return ans
}
python3 解法, 执行用时: 76 ms, 内存消耗: 19.6 MB, 提交时间: 2023-06-01 10:09:28
# 哈希表 + 逐一统计
class Solution:
def subarraysDivByK(self, nums: List[int], k: int) -> int:
record = {0: 1}
total, ans = 0, 0
for elem in nums:
total += elem
modulus = total % k
same = record.get(modulus, 0)
ans += same
record[modulus] = same + 1
return ans