[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

	class Solution {
	fun subarraysDivByK(nums: IntArray, k: Int): Int {
	val map = mutableMapOf<Int,Int>()
	map[0] = 1 // sum = 0 can be divided by any k
	var sum = 0
	var key = 0
	var ans = 0
	for(n in nums) {
	sum += n
	key = sum % k
	if(key < 0) {
	key += k
	}
	if(map[key] == null) {
	map[key] = 1
	} else {
	ans += map[key]!!
	map[key] = map[key]!! + 1
	}
	}
	return ans
	}
	}

view raw continuous_subarray_sum.kt hosted with ❤ by GitHub