面试题:x,y,z是一个整数数组的三个不同的元素，找到所有x = y +z的组合 ?

Question

题目：x,y,z是一个整数数组的三个不同的元素，找到所有x = y +z的组合,在实现题目要求的基础上尽可能使用更优的算法.

我的实现代码：

$arr = [1, 2, 5, 6, 7];
foreach ($arr as $value) {
    foreach ($arr as $val) {
        if ($val == $value) {
            continue;
        }
        $sum = $value + $val;
        if ($sum != $value && $sum != $val && in_array($sum, $arr)) {
            echo "$sum = $value + $val <br>";
        }
    }
}

还有更优的实现方式吗？

Answer 1

稍优化了一点，按你的算法，有n个元素的数组，要循环

n * n * in_array里的次数，in_array内部也是循环

var arr = [1, 2, 5, 6, 7];//如果这个数组不是有序数组，哪还要先加排序
var len =arr.length

let result=[]
let count=0

for(let a=0;a<len;a++){
let max = arr.pop()
let newlen = arr.length
for(let i=0;i<newlen-1;i++){
   if(arr[i]+arr[i+1]> max){
    break;
  }
  for(let j=i;j<newlen-1;j++){
    let plus = arr[i]+arr[j+1]
    count++
    if(plus>max){
      break;
    }
    if(plus==max){
      result.push([max,arr[i],arr[j+1]])
    }
  }
}
}
console.log(result)//输出结果
console.log(count)//输出总循环次数，

回复里说的好，我没有考虑负数的情况，如果要考虑负数，哪把最大数pop出来，就不行了，只能重新维护一条新数组，用来枚举所有值，修改如下

var arr = [-8, -1, 1, 2, 5, 6, 7];//如果这个数组不是有序数组，哪还要先加排序
var len =arr.length
var arr1 = [...arr] //复制一条新数组
let result=[]
let count=0

for(let a=0;a<len;a++){
let max = arr1.pop()// 从新数组中枚举各个值。
let newlen = arr.length
for(let i=0;i<newlen-1;i++){
   if(arr[i]+arr[i+1]> max){
    break;
  }
  for(let j=i;j<newlen-1;j++){
    let plus = arr[i]+arr[j+1]
    count++
    if(plus>max){
      break;
    }
    if(plus==max){
      result.push([max,arr[i],arr[j+1]])
    }
  }
}
}
console.log(result)//输出结果
console.log(count)//输出总循环次数，
输出
[[7, 1, 6], [7, 2, 5], [6, -1, 7], [6, 1, 5], [5, -1, 6], [1, -1, 2], [-1, -8, 7]]