0974. Subarray Sums Divisible by K

题目信息

题号:

0974

难度:

Medium

主题:

数组、连续子数组、整除计数

原题:

LeetCode 0974

重点:

统计所有非空连续子数组实例,其元素和必须能被正整数 k 整除;数组允许包含负数和零

题目重述

给定整数数组 nums 和正整数 k。请统计有多少个非空连续子数组的元素总和能够被 k 整除,即总和除以 k 的余数为 0。

子数组由起止下标确定,不同下标范围分别计数。元素可以为负数,和为 0 的子数组也满足整除条件。

1 <= nums.length <= 3 * 10^4,-10^4 <= nums[i] <= 10^4,2 <= k <= 10^4。

自建示例

负数使多个区间的和成为三的倍数:

输入:nums = [2,-2,3,1], k = 3
输出:3
解释:合法子数组为 nums[0..1],和为 0;nums[0..2],和为 3;以及 nums[2..2],和为 3。

全部元素都是零:

输入:nums = [0,0,0], k = 2
输出:6
解释:三个单元素、两个长度为 2 的区间和整个数组的和都为 0,因此六个非空子数组全部满足整除条件。