Shulou(Shulou.com)06/01 Report--

This article mainly shows you the "LeetCode how to return the sum of an integer array of elements can be divided by K number of subarrays", the content is easy to understand, well-organized, hope to help you solve your doubts, the following let Xiaobian lead you to study and learn "how LeetCode returns the sum of elements of an integer array can be divisible by K" of this article.

one

Topic description

Given an integer array A, returns the number of (continuous, non-empty) subarrays in which the sum of elements is divisible by K. Such as input

A = [4, 5, 5, 0, and 1], K = 5, returns 7 (because the sum of 7 consecutive subarrays is divisible by 5).

two

Answer to the question

Idea: the hash table is similar to the subarray of LeetCode exercises DAY 17: and k. If pre (I) is defined as the sum of all the elements in [0mai], then there is a relation pre (I) = pre (iMul 1) + A [I], and find out how many (pre (I)-pre (jmer1)) can be divisible by K. First of all, I would like to introduce the congruence theorem.

Congruence theorem: let m be a positive integer greater than 1, and an and b are integers. If m | (a mod b), then an and b are said to be congruence with respect to module m, denoted as a ≡ b (congruence m).

In this question, there is (pre (I)-pre (jmur1)) | K is equivalent to pre (I) ≡ pre (JMQ 1) (mod K), so we can create a hash table in which the remainder is the key and the number of occurrence of the remainder is the value, and we can calculate the sum of the key corresponding values in the hash table that are the same as those of pre (I) | K.

Class Solution: def subarraysDivByK (self, A: List [int] K: int)-> int: h_map = {0:1} a = 0 ans = 0 for i in range (len (A)): a + = A [I] if a% K in h_map: ans + = h _ map [a% K] h _ map [a% K] + = 1 else: H _ map [a% K] = 1 return ans

These are all the contents of the article "how LeetCode returns the sum of the elements of an integer array that can be divisible by K". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.