[LeetCode] 523. Continuous Subarray Sum

轉自LeetCode

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 1:

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.

Example 2:

Input: [23, 2, 6, 4, 7],  k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

Note:

1. The length of the array won't exceed 10,000.
2. You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

<Solution>
這題需要用到一個數學定理來解

如果 a / c 和 b / c 的餘數相同，則 (a - b) 一定可以被 c 整除

根據上面的定理，解題思路如下

• 歷遍 nums，並計算當下的總和

• 如果 table[ sum % k ] 存在，代表之前有一個 subarray 的和除以 k 的餘數，和目前的總和除以 k 的餘數相同，所以兩個和相減後所產生的和(等於某個 subarray 的和) 一定是 k 的倍數。因此，把 table 對應的 value，也就是該和最終所在的 index 相減，看看最後的 subarray 的 size 是否大於 2

• 如果 table[ sum % k ] 不存在，那麼記錄對應的 index

code 如下(參考資料)

C++

Java


Kotlin