时间戳

首页 > 解决方案 > 如何在添加到javascript中的目标数字的唯一整数数组中查找元组

javascript - 如何在添加到javascript中的目标数字的唯一整数数组中查找元组

问题描述

我正在尝试用 Javascript 解决 Advent of Code 2020 的第一个问题。我的任务是找到三个添加到目标数字的数字。在这种情况下，目标是 2020 年。

例如：应该有三个数字：[1721, 979, 366, 299, 675, 1456]加到​​ 2020 年。在这种情况下，这些数字是[366, 675, 979]

我的方法：通过对数组进行排序，可以提高算法的效率。这种有效的方法使用两指针技术。遍历数组并修复三元组的第一个元素。现在使用两个指针算法来查找是否存在总和等于 x – array[i] 的对。两个指针算法需要线性时间，因此它比嵌套循环更好。

算法：对给定的数组进行排序。循环遍历数组并修复可能的三元组的第一个元素 arr[i]。然后固定两个指针，一个在 i + 1，另一个在 n - 1。查看总和，如果总和小于所需总和，则增加第一个指针。否则，如果总和较大，则减小结束指针以减少总和。否则，如果两个指针处的元素之和等于给定的和，则打印三元组并中断。

注意：我正在从 python 线程扩展这种方法并且非常喜欢它，但是在尝试在 javascript 中创建它时，我遇到了一些麻烦。

目前，这就是我所拥有的：


function threeSumBest(array, target) {

    // sort elements (accending)
    const sortedAsc = array.sort((a, b) => a - b)


    for (let i = 0; i < sortedAsc.length; i++) {
        let result = []

        // index of the first element in the remaining elements 
        let firstElement = i + 1

        // # index of the last element 
        let lastElement = sortedAsc.length - 1

        // create a sum variable
        let sum = (sortedAsc[i] + sortedAsc[firstElement] + sortedAsc[lastElement])

        // console.log(sortedAsc[i], sortedAsc[firstElement], sortedAsc[lastElement], sum);
        // console.log(sortedAsc[i], sortedAsc[firstElement], sortedAsc[lastElement]);
        console.log(result);

        if (sum > target) {
            console.log('greater than');
            lastElement--
        }
        if (sum < target) {
            console.log('less than');
            result[0] = sortedAsc[i++]
            result[1] = sortedAsc[firstElement]
            result[2] = sortedAsc[lastElement]
        }
        if (sum == target) {
            console.log('equal');
        }
    }
}

console.log(threeSumBest([1721, 979, 366, 299, 675, 1456], 2020))

标签： javascriptarraysalgorithmtuples

解决方案

您缺少将 firstIndex 迭代到 lastIndex 的内部循环。以下代码将为您工作

for (let i = 0; i < sortedAsc.length; i++) {
    let result = []

    // index of the first element in the remaining elements 
    let firstElement = i + 1

    // # index of the last element 
    let lastElement = sortedAsc.length - 1
    while(firstElement<lastElement){
        let sum = (sortedAsc[i] + sortedAsc[firstElement] + sortedAsc[lastElement])
        if (sum > target) {
            //console.log('greater than');
            firstElement++;
        }
        if (sum < target) {
            //console.log('less than');
            lastElement--;
        }
        if (sum == target) {
            result[0] = sortedAsc[i]
            result[1] = sortedAsc[firstElement]
            result[2] = sortedAsc[lastElement]
            console.log('equal');
            break;
        }
    }
}

console.log(threeSumBest([1721, 979, 366, 299, 675, 1456], 2020))

推荐阅读