java - 扫描数组中可被 3 整除的最长子数组的长度

Question

我正在编写一个程序，它扫描一个数组并生成包含总和可被 3 整除的元素的最长子数组的长度。我已经使用了另一个问题中的概念，使用前缀和概念 - 扫描第一个和最后一个求和，通过 modolu 3 给出 0,1,2，计算每组之间的差异并返回三组中最大的一个。

我决定使用随机数组生成器来测试它。 90% 的情况下它都有效，但在其他情况下它会错过几个数字的正确答案。 知道出了什么问题吗？

我已经包含了一个测试器，其中包含一个执行相同操作的低效方法。附图片:

输出:

84|4|94|27|85|10|87|11|66|34|66|42|26|65|12|93|14|

array size is: 17

Bad What: 15

My What: 13

代码:

import static java.lang.Math.*;
import java.util.Random;

 public class Q1 {
    public static void main(String args[]) {
        Random rand = new Random();
        int[] a = new int[rand.nextInt(100)];
        for (int i = 0; i < a.length; i++)
        {
            a[i] = rand.nextInt(100);
            System.out.print(a[i] + "|");
        }
        System.out.println();
        System.out.println("array size is: " + a.length);
        System.out.println("Bad What: " + badWhat(a));
        System.out.println("My What: " + what(a));
    }

    public static int what(int[] a) {
        int sumLeft = 0, sumRight = 0;
        int zero, one, two;
        int firstZero = 0, firstOne = 0, firstTwo = 0, lastZero = 0, lastOne = 0, lastTwo = 0;
        for (int i = 0; i < a.length; i++) {
            sumLeft += negMod(a[i])%3;
            sumRight += negMod(a[a.length - 1 - i]%3);
            if ((sumLeft) % 3 == 0)
                firstZero = i;
                if ((sumRight) % 3 == 0)
                    lastZero = i;
                if ((sumLeft) % 3 == 1)
                    firstOne = i;
                if ((sumRight) % 3 == 1)
                    lastOne = i;
                if ((sumLeft) % 3 == 2)
                    firstTwo = i;
                if ((sumRight) % 3 == 2)
                    lastTwo = i;
            }
        firstOne++;
        firstTwo++;
        zero = lastZero - firstZero + 1;
        one = lastOne - firstOne;
        two = lastTwo - firstTwo;
        int result = max(max(zero, one), two);
        if (firstZero +1 > result)
            result = ++firstZero;
        return result;
    }

    public static int negMod (int a)
    {
        if (a<0)
        {
            return (a+3);
        }
        return a;
    }

    public static int f (int[] a, int low, int high)
    {
        int res = 0;
        for (int i = low; i<=high; i++)
            res += a[i];
        return res;
    }

    public static int badWhat (int[] a)
    {
        int temp = 0;
        for (int i =0; i< a.length; i++) {
            for (int j = i; j < a.length; j++) {
                int c = f(a, i, j);
                if (c % 3 == 0) {
                    if (j - i + 1 > temp)
                        temp = j - i + 1;
                }
            }
        }
        return temp;
    }
}

Answer 1

一个明显的错误是，您使用的是 sumLeft += negMod(a[i])%3; 而不是 sumLeft += negMod(a[i] % 3);.

看来您的算法存在很多问题。首先，在 sumRight 中，您应该包含从第一个元素到当前元素的总和，但您包含的是从当前元素到最后一个元素的总和。因此，您的解决方案能够在某些测试中发挥作用真是幸运。

其次，您应该找到具有特定模数的第一个子数组和最后一个子数组。因此，一旦找到该值，您就不需要覆盖它。

这应该有效:

public static int what(int[] a) {
    if (a.length == 0) {
        return 0;
    }

    int sumLeft = 0, sumRight = 0;
    for (int el : a) {
        sumRight += el % 3;
    }
    sumRight = negMod(sumRight % 3);

    int firstZero = a.length, firstOne = a.length, firstTwo = a.length,
            lastZero = -1, lastOne = -1, lastTwo = -1;
    for (int i = 0; i < a.length + 1; i++) {
        if (sumLeft % 3 == 0 && firstZero == a.length)
            firstZero = i;
        if (sumRight % 3 == 0 && lastZero == -1)
            lastZero = a.length - 1 - i;
        if (sumLeft % 3 == 1 && firstOne == a.length)
            firstOne = i;
        if (sumRight % 3 == 1 && lastOne == -1)
            lastOne = a.length - 1 - i;
        if (sumLeft % 3 == 2 && firstTwo == a.length)
            firstTwo = i;
        if (sumRight % 3 == 2 && lastTwo == -1)
            lastTwo = a.length - 1 - i;
        sumLeft += negMod(a[min(i, a.length - 1)] % 3);
        sumRight = negMod(sumRight - a[max(a.length - 1 - i, 0)] % 3);
    }
    int zero = lastZero - firstZero + 1;
    int one = lastOne - firstOne + 1;
    int two = lastTwo - firstTwo + 1;
    Integer[] options = new Integer[]{zero, one, two, 0};
    return Collections.max(Arrays.asList(options));
}