可被k整除的子阵列数

Question

我在一次面试中有以下问题，尽管我给出了一个可工作的实现，但它不够高效。

数组A的切片是任何一对整数（P，Q），使得0≤ P≤ Q

我被要求编写的函数必须返回可被K整除的切片数。预期的时间复杂度为O（max（N， K）），空间复杂度为O（K）。

我的解决方案是最简单的，一个循环套一个循环，检查每一个切片:O(n^2)

我一直在想，但我真的不知道如何在O（max（N， K））中做到这一点。

它可能是子集和问题的变体，但我不知道如何计算每个子数组。

编辑：数组中的元素可以是负片。下面是一个例子：

A = {4, 5, 0, -2, -3, 1}, K = 5

Function must return 7, because there are 7 subarrays which sums are divisible by 5
{4, 5, 0, -2, -3, 1}
{5}
{5, 0}
{5, 0, -2, -3}
{0}
{0, -2, -3}
{-2, -3}

Answer 1

示例：-

输入阵列

int [] nums = {4,3,1,2,1,5,2};

K是3

连续求和

4,7,8,10,11,16,18

将上面的连续和数组除以3

1,1,2,1,2,1,0

我们有四个1两个2一个0

所以总数是（4*3）/2（2*1）/2（2*1）/2=8

(4*3)/2来自于从四个1中选择任意两个1，即nC2 = n(n-1)/2

这是节目单

公共静态长计数SubArrayDivByK（int k， int[]nums）{

    Map<Integer, Integer> modulusCountMap = new HashMap<Integer, Integer>();
    int [] consecSum = new int[nums.length];
    consecSum[0]=nums[0];

    for(int i=1;i<nums.length;i++){
        consecSum[i]= consecSum[i-1] +nums[i];
    }

    for(int i=0;i<nums.length;i++){
        consecSum[i]= consecSum[i]%k;

            if(consecSum[i]==0 && modulusCountMap.get(consecSum[i])==null){
                modulusCountMap.put(consecSum[i], 2);
            }else{
                modulusCountMap.put(consecSum[i], modulusCountMap.get(consecSum[i])==null ? 1 : modulusCountMap.get(consecSum[i])+1);
            }

    }

    int count = 0;

    for (Integer val : modulusCountMap.values()) {
        count = count +  (val*(val-1))/2;
    }

    return count;
}

以上优化版

static long customOptimizedCountSubArrayDivByK(int k, int[] nums) {

        Map<Integer, Integer> modulusCountMap = new HashMap<Integer, Integer>();
        int [] quotient = new int[nums.length];
        quotient[0]=nums[0]%3;



        if(quotient[0]==0){
            modulusCountMap.put(quotient[0], 2);
        }else{
            modulusCountMap.put(quotient[0], 1);
        }


        for(int i=1;i<nums.length;i++){
            quotient[i]= (quotient[i-1] + nums[i])%3;


                if(quotient[i]==0 && modulusCountMap.get(quotient[i])==null){
                    modulusCountMap.put(quotient[i], 2);
                }else{
                    modulusCountMap.put(quotient[i], modulusCountMap.get(quotient[i])==null ? 1 : modulusCountMap.get(quotient[i])+1);
                }

        }

        int count = 0;

        for (Integer val : modulusCountMap.values()) {
            count = count +  (val*(val-1))/2;
        }

        return count;
    }

Answer 2

这是@Thomash提出的解决方案的Java实现。

第二个循环不是必须的，因为我们可以直接用当前值增加答案，然后递增。

为了避免负数组索引，我们还必须调整模块计算。

public static int countSubarrays(int[] nums, int k) {
    int[] cache = new int[k];
    cache[0]++;
    int s = 0, counter = 0;
    for (int i = 0; i < nums.length; i++) {
        s = ((s + nums[i]) % k + k) % k;
        counter += cache[s];
        cache[s]++;
    }

    return counter;
}

Answer 3

由于您只对可被K整除的数字感兴趣，因此您可以模数K进行所有计算。考虑累积和数组S，使得S[i]=S[0]S[1]... S[i]。然后（P， Q）是一个可被K整除的切片iffS[P]=S[Q]（记住我们以模K进行所有计算）。所以您只需计算[0，...， K-1]的每个可能值在S中出现的次数。

下面是一些伪代码:

B = new array( K )
B[0]++
s = 0
for i = 0 to N - 1
  s = ( s + A[i] ) % K
  B[s]++
ans = 0
for i = 0 to K - 1
  ans = ans + B[i] * ( B[i] - 1 ) / 2

一旦您知道它们是S中具有值i的x个单元格，您需要计算从值i的单元格开始到值i的单元格结束的切片数，这个数是x（x-1）/2。为了解决边缘问题，我们添加一个值为0的单元格。

x（x-1）/2代表什么：假设我们的数组是[4,5,0]，4作为前缀和的频率是x，在这种情况下是3。现在，我们可以从x的值得出结论，至少有x-1个数可以被k整除，或者mod k等于0。现在，这些x-1数中的所有可能子数组是1 2 3…（x-1），即（（x-1）*（（x-1）1）/2（从1到N求和的标准公式，其中N代表（x-1）。