在数组中找到最大的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
}

如何处理数组中的负数值？

- metamorph_online

---

这些答案中有满意的吗？如果有，请用接受的勾选标记一个，并点赞。 - Aaron Plocharczyk

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

然后，再次遍历每一对索引 k,l，并检查 sumsMap 中是否存在键 arr[l]-arr[k]（d-c）或 arr[k]-arr[l]（c-d）。如果存在且索引 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] ))

- Anatolii

Answer 2

我为您将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; 
    }
} 

- Aaron Plocharczyk