给定一个数组,计算总和为60的倍数的对

Question

给定一个数组,如何找到加起来为60的一对(两个值)或一个可被60整除的值.注意:必须比O(N ^ 2)快.

输入:[10,50,30,90]输出:2推理:10 + 50 = 60,30 + 90 = 120(120可被60整除)

输入:[60,60,60]输出:3推理:60 + 60 = 120,60 + 60 = 120,60 + 60 = 120

我下面的代码将在O(N)时间内运行,但我不知道如何处理彼此相等的对(即如果你在数组中有2 30个值会给你的计数器加1 ,但是如果你在数组中有3 30个值可以为你的计数器增加3个).我想我应该创建一个组合函数(即2C2或3C2),但这是一个线性函数,并不会只是使函数回到O(N ^ 2)？

values(myList) {
    var obj = {};
    var count = 0;

    // loop through array and mod each value and insert it into a dictionary
    myList.forEach((elem, index) => {
        if (!obj.hasOwnProperty(elem % 60)) {
            obj[elem % 60] = 1;
        } else {
            obj[elem % 60]++;
        }
    });

    for (var keys in obj) {
        if (obj.hasOwnProperty(60 - keys)) {
            if (60 - keys == keys) {
                // take care of pairs
                // obj[keys] = x --> xC2
            } else {
                count += Math.min(obj[keys], obj[60 - keys]);
                delete obj[keys]
                delete obj[60 - keys];
            }
        }
    }
    return count;
}

Answer 1

无需组合。这是简单的数学。

它是n * (n-1) / 2。

假设您有 4 件商品a, b, c, d。

对将是：

• (一、二)
• （一、三）
• （广告）
• （公元前）
• (b、d)
• （光盘）

对于4 个项目，我们有4 * 3 / 2 = 6。

＃更新：

改变

count += Math.min(obj[keys], obj[60 - keys]);

到

count += obj[keys] * obj[60 - keys];

考虑 2 个键12- 和48。

• 密钥12包含元素 - 12,72,132
• 密钥48包含元素 - 48,108

从技术上讲，您正在存储它们的计数，即 3 和 2。如果您观察，总数是多少。我们可以组成的对是3 * 2 = 6而不是 Math.min(3,2);