javascript - 给定一个整数数组返回正数，其中存在等效的负数

Question

我已经使用两个循环在 javascript 中实现了解决方案，下面是代码

function getNums(arr){
 var res = [];
 var found = {};
 var i, j;
 var arrLen = arr.length;

 for(i=0; i<arrLen; i++){
   if(!found.hasOwnProperty(arr[i])){
    for(j=0; j<arrLen; j++){
      if(arr[i]+arr[j] === 0){
        var num = arr[i];
        if(num > 0){
            res.push(num);
          found[num] = 1;
        }
      }
    }
   }
 }
 return res;
}

console.log(getNums[-1, -2, 0, -4, 1, 4, 6]); // Output: [1, 4]

时间复杂度为O(n2)。有人可以建议更好的解决方案/在上面改进以降低复杂性吗？

Answer 1

您可以只将数组添加到集合中，然后过滤以包含在集合中。确定某物是否在集合中是常数时间:

let arr = [-1, 2, 3, 1 , 3, -3, 4, -6]
let s = new Set(arr)

// all positive numbers with corresponding negatives in the set
let filtered = arr.filter(item => item > 0 && s.has(-1 * item))
console.log(filtered)

另一种方法是对数组进行排序，然后沿着数组向上移动两个指针，同时进行匹配。结果将被排序，但是，这可能与原始数组的顺序不同:

let arr = [-2, -3, 2, 5, 3, 1, -6, 2, -5]
arr.sort()

// get startig indexes
let i = 0, j = arr.findIndex(n => n > 0)
let res = []
if (j > -1) { // only if there are positive numbers in the array
    while(arr[i] < 0 && j < arr.length){
        if (-1 * arr[i] === arr[j]){
            res.push(arr[j++])
        } else if(-1 * arr[i] > arr[j]){
            j++
        } else if(-1 * arr[i] < arr[j]){
            i++
        }
    }
}
console.log(res)