javascript - 在数组中找到最大的 d 使得 a + b + c = d

Question

任务给定一个排序的整数数组 arr。它包含几个唯一的整数(负数、正数或零)。

你的任务是找到最大的 d 使得 a + b + c = d，其中 a、b、c 和 d 是 arr 的不同元素。如果没有找到这样的元素 d，则返回 null。

示例:

对于 arr = [2,3,5,7,12]，输出应该是 12(这个数组正确地传递了我的函数)

对于arr = [-100,-1,0,7,101]，输出应该是0(这个不通过)

我可以管理正数检查，但我的函数因负数而失败

function findD(arr) {

    myArr = arr.sort((a, b) => b - a);

    for (var i = 0; i < myArr.length; i++) {

        for (var k = i + 1; k < myArr.length - 2; k++) {

            var j = k + 1,
                d = myArr.length - 1;

            while (j < d) {

                let sum = myArr[k] + myArr[j] + myArr[d];

                if (sum == myArr[i]) {
                    return myArr[i];
                } else if (sum < myArr[i]) {
                    d--;
                } else if (sum > myArr[i]) {
                    j++;
                }
            }
        }
    }
    return null
}

如何处理数组中的负值？

Answer 1

让我们假设有一个像 [-2, -1, 0, 3] 这样的数组.

然后，根据您的算法按降序排序后，它将是 [3, 0, -1, -2] .显然，您的算法只会选择 3正如你假设的那样 d必须大于其余 3 处的数字职位。那当然是错误的。你不应该假设 a , b和 c一定小于 d .这就是为什么你必须在 d 时检查其他情况。占据与a,b,c相关的所有可能位置.所以，首先考虑一个蛮力方法，它将有 O(n^4)时间和O(1)空间复杂度:

...
for (var i = myArr.length; i >= 0 ; i--) {
    for (var k = 0; k < myArr.length; k++) {
        if (k == i) {
            continue
        }
        for (var j = k + 1; j < myArr.length; j++) {
            if (j == i) {
                continue
            }
            for (var d = j + 1; d < myArr.length; d++) {
                if (d == i) {
                    continue
                }
                if (myArr[i] == myArr[k] + myArr[j] + myArr[d]) {
                    return myArr[i]
                }     
            }
        }
    }
}
return null 
...

但是这个问题可以在O(n^2)中解决时间和O(n^2)空间。

首先我们应该意识到 a + b = d - c .

因此，对于给定的数组 arr和每对索引 i,j: i<j我们存储arr[i] + arr[j] ( a + b ) 作为键和对 i,j作为 sumsMap 中值的一项(该值是索引对的列表) .该值必须是一个列表，因为可以有几对索引对应于相同的总和 a + b .

然后，再次遍历每一对索引k,l并检查是否有一个键 arr[l] - arr[k] ( d - c ) 或 arr[k] - arr[l] ( c - d ) 存在于 sumsMap 中.如果是，索引 l,k与sumsMap[s]中的不同然后更新最大元素，如果它低于 arr[l] .

function solve(arr) {
    var sumsMap = {}
    for (var i = 0; i < arr.length; i++) {
        for (var j = i + 1; j < arr.length; j++) {
            var sum = arr[i] + arr[j]
            
            // several pairs of indices can correspond to the same summ so keep all of them
            var mappedIndices = sumsMap[sum]
            if (typeof mappedIndices == "undefined") {
                mappedIndices = []
            }
            let pair = {}
            pair.first = i
            pair.second = j
            mappedIndices.push(pair)
            
            sumsMap[sum] = mappedIndices
        }
    }    

    var maxD = Number.MIN_SAFE_INTEGER
    for (var k = 0; k < arr.length; k++) {
        for (var l = 0; l < arr.length; l++) {
            mappedIndices = sumsMap[arr[l] - arr[k]]
            
            if (mappedIndices != undefined) {
                // in the worst case, 4 pairs of indices may contain k or l but the fifth one won't as numbers in the array are unique and hence the same index can occur only twice 
                var steps = Math.min(5, mappedIndices.length)
                for (var s = 0; s < steps; s++) {
                    var pair = mappedIndices[s]
                    if (pair.first != k && pair.first != l && pair.second != k && pair.second != l) {
                        maxD = Math.max(maxD, arr[l])    
                    }
                }
            }
        }
    }
    
    if (maxD == Number.MIN_VALUE) {
        return -1
    } else {
        return maxD
    }
}

document.write(solve([-100,-1,0,7,101] ))
document.write("<br>")
document.write(solve([-93,-30,-31,-32] ))