找出数组中最大的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

我把Renaldo建议的函数从https://www.geeksforgeeks.org/find-largest-d-in-array-such-that-a-b-c-d/翻译成了JavaScript。

function findLargestd(S, n){ 
    var found = false;

    // sort the array in 
    // ascending order 
    S.sort((a, b) => a - b); 

    // iterating from backwards to 
    // find the required largest d 
    for(var i = n - 1; i >= 0; i--){ 
        for(var j = 0; j < n; j++){ 

            // since all four a, b, c,  
            // d should be distinct 
            if(i == j){
                continue;
            } 

            for(var k = j + 1; k < n; k++){ 
                if(i == k){
                    continue;
                }

                for(var l = k + 1; l < n; l++){ 
                    if(i == l){
                        continue;
                    } 

                    // if the current combination   
                    // of j, k, l in the set is  
                    // equal to S[i] return this  
                    // value as this would be the  
                    // largest d since we are   
                    // iterating in descending order  
                    if(S[i] == S[j] + S[k] + S[l]){ 
                        found = true; 
                        return S[i]; 
                    } 
                } 
            } 
        } 
    } 

    //if not found, return 0
    if(found === false){
        return 0; 
    }
} 

Answer 2

假设有一个像< code>[-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）空间中解决。

首先，我们应该认识到。

因此，对于给定的数组 ar 和每对索引 i，j： i

然后，再次遍历每对索引 k，l 并检查总和映射中是否存在键阿瑞[l] - 阿瑞[k] （d - c） 或阿瑞[k] - 阿瑞[l] （c - d）。如果是这样，并且索引 l，k 与 summap 中的索引不同，则更新最大元素（如果它低于 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] ))