求和可被K整除的最长子数组

Question

求其和可被K整除的最长子数组。在O(n)中可能吗？如果不是，它能比n^2更好地完成吗？

Answer 1

    as rightly pointed out by @IVIad you have to keep a track of the current 
sum modulo k. 
you can write it as s=0
          s=(s+arr1[i])%k 
    after that in a for loop you can use a dictionary and see if the 
s is present in dictionary ; 
if yes then update the length else update the dictionary .
    below is the code.


    def longestsubsarraywithsumdivisiblebyk(arr1,k):
        h={}
        h[0]=-1
        maxlen=0
        s=0
        for i in range(len(arr1)):
            s=(s+arr1[i])%k
            if s in h:
                maxlen=max(maxlen,i-h[s])
            else:
                h[s]=i
        return maxlen