[LeetCode] 974. Subarray Sums Divisible by K

轉自LeetCode

Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.

A subarray is a contiguous part of an array.

 

Example 1:

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Example 2:

Input: nums = [5], k = 9
Output: 0

 

Constraints:

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• 2 <= k <= 104

Solution

這題可以看成 523. Continuous Subarray Sum 的衍生題，這次要求的是數量

而且數值可以有負數，所以這個部分要再特別處理一下

首先，先來看一下怎麼計算次數

從 523 那題可以知道，如果 a % k = 1，b % k = 1, 那麼 a - b % k = 0 且 b - a % k = 0

因此，紀錄 sum % k 出現的次數

如果相同的餘數已經出現過 1 次，那代表目前最新的 sum2

可以和之前那一次的 sum1 產生一個 sum' 能被 k 整除

如果相同的餘數出現過兩次，代表目前最新的 sum3可以和 sum1 以及 sum2 各產生新的 sum 來被 k 整除

等同於加上 map[sum % k] 的數字

接著，來注意一下當餘數是負值的時候

舉例 -6 % 5 = -1，可以看成 -6 = -1 * 5 - 1

但如果把餘數加上 5，變成 4，這時可以看成，-6 = -2 * 5 + 4

物理意義就是，多一個五出來，原本是 -1 * 5，變成 -2 * 5，而這樣的結果會保證餘數是正值

kotlin