找到最长子阵列，其总和整除被K [英] Find longest subarray whose sum divisible by K

问题描述

找到最长子阵列，其总和整除K. 它可以在O（n）的？ 如果不是可以把它更好的完成则n ^ 2？

find longest subarray whose sum divisible by K. It is possible in O(n)? If not can it be done in better then n^2 ?

推荐答案

让 S [I] =的第i个元素之和模氏/ code>。

Let s[i] = sum of first i elements modulo K.

我们有：

s[i] = (s[i - 1] + a[i]) % K

我们必须找到，每个我，最小的Ĵ，使得取值[我] == S [J] 。您可以通过散列 S [I] 价值发现这一点。如果 K 小，你可以只保留一个数组 P [I]为其=第一位置S [K] ==我。

We have to find, for each i, the smallest j such that s[i] == s[j]. You can find this by hashing the s[i] values. If K is small, you can just keep an array p[i] = first position for which s[k] == i.

复杂度 O（N）。

这篇关于找到最长子阵列，其总和整除被K的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！