找到 3 个数字的最大和，也可以被 3 整除

Question

如何找到也可以被 3 整除的 3 个数字的最大和？
例子：
输入： [1， 15， 4， 7， 2]
输出： [15， 7， 2] (按此顺序(

输入： [1， 2， 4， 7]
输出： [1， 4， 7] (按此顺序(

我只想到了这个：

function largestSum(arr) {
    let max = -1;
    let nums;
    for (let i = 0; i < arr.length; i++)
        for (let j = i + 1; j < arr.length; j++)
            for (let k = j + 1; k < arr.length; k++)
                if ((arr[i] + arr[j] + arr[k]) % 3 === 0 && arr[i] + arr[j] + arr[k] > max)
                    nums = [arr[i], arr[j], arr[k]], max = arr[i] + arr[j] + arr[k];
    return nums;
}

但是，这不是更好的选择(效率更高(吗？

Answer 1

这可以使用模算术在线性和恒定空间中求解，无需对输入进行排序或枚举其组合。

Save:
  the largest three elements congruent to 0 mod 3
  the largest three elements congruent to 1 mod 3
  the largest three elements congruent to 2 mod 3
Choose the largest of:
  1. the sum of the largest three elements congruent to 0 mod 3
  2. the sum of the largest three elements congruent to 1 mod 3
  3. the sum of the largest three elements congruent to 2 mod 3
  4. the sum of the largest element congruent to 0 mod 3
                and the largest element congruent to 1 mod 3
                and the largest element congruent to 2 mod 3

Answer 2

不敢相信有一种方法可以在不尝试数组的所有组合的情况下做到这一点 [你已经做了什么]

Answer 3

如果首先按降序对数字进行排序，然后找到可被三整除的第一个解，这将是最大值。

在最坏的情况下，它比您的解决方案更糟糕，因为它可以完成您所做的一切以及排序，但在最好的情况下，它可能是一种排序和一种测试。

它使用的是贪婪算法。

Answer 4

另一个简单的解决方案，具有简单的组合算法并检查所需的参数。

function getCombinations(array) {
    function add(a, b) { return a + b; }
    function fork(i, t) {
        var sum = t.reduce(add, 0);
        if (i === array.length) {                
            if (t.length === 3 && sum % 3 === 0 && sum > result.reduce(add, 0)) {
                result = t;
            }
            return;
        }
        fork(i + 1, t.concat([array[i]]));
        fork(i + 1, t);
    }
    var result = [];
    fork(0, []);
    return result;
}
console.log(getCombinations([1, 15, 4, 7, 2]));
console.log(getCombinations([1, 2, 4, 7]));

.as-console-wrapper { max-height: 100% !important; top: 0; }