阵列和子阵列

Question

给定一个大小为n的数组及其元素，找出其和可与给定数k整除的最大子序列(具有给定顺序的元素)。

我在O(n^2)中用蛮力解决了这个问题，但n是15万，而且我的解不够快。我想知道这个问题是否有更好的解决办法。请解释一下你的回答！

Answer 1

最有效的方法是使用散列。

1. 如果给定数组的长度为奇数，则返回false。奇数长度数组不能成对分割。
2. 遍历输入数组并计数所有残余物的出现情况。freq[arri % k]++
3. 再次遍历输入数组。a) Find remainder of current element. b) If remainder divides k into two halves, then there must be even occurrences of it as it forms pair with itself only. c) If remainder is 0, then then there must be even occurrences. d) Else, number of occurrences of current remainder must be equal to number of occurrences of "k - current remainder".