java - TripleSum 计算 O(n) 时间的算法，Java

Question

手头的任务是提出一个算法，该算法接受一个非负整数数组，并根据该数组是否包含 3 个加起来为 225 的数字返回一个 boolean 值。

困难的部分是写这个是 O(n) 时间。

有人有什么想法吗？

Answer 1

因为我现在不在电脑旁，所以只是大声地想出 ATM，但是怎么样:

记录每个数字后扫描数字 - 丢弃任何大于 225 的数字。

执行一次计数以确定答案。

必须是 O(n)，因为我们传递了一次原始进位 - 其余的是 O(225)，它消失了。

已添加 - 现在我有了一台电脑。

我错过了一些边缘情况，但这看起来是该算法的一个公平实现:

boolean canAdd3ToMakeX(int[] v, int x) {
    // How many of each number.
    int[] counts = new int[x];
    // O(n) part.
    for (int i = 0; i < v.length; i++) {
        if (v[i] >= 0 && v[i] < x) {
            counts[v[i]] += 1;
        }
    }
    // O(k) part. :) - NOT the most efficient - but the most obvious.
    for (int a = 0; a < x; a++) {
        for (int b = 0; b < x; b++) {
            for (int c = 0; c < x; c++) {
                if (a + b + c == x && counts[a] > 0 && counts[b] > 0 && counts[c] > 0) {
                    return true;
                }
            }
        }
    }

    return false;
}

private void test(int[] t) {
    System.out.println("Can - " + Arrays.toString(t) + " = " + canAdd3ToMakeX(t, 225));
}

public void test() {
    test(new int[]{1, 2, 3, 4, 5, 5, 5, 5, 5});
    test(new int[]{1, 2, 222});
    test(new int[]{100, 100, 25});

}

它确实为我的测试用例提供了正确的答案，但我认为我的解决方案存在问题，无法将其作为家庭作业提交。我将这些问题的解决方案留给了学生(提示:尝试 test(new int[]{100, 25})。