我的算法有点过时，效率极低 [英] My algorithm is a bit off and super inefficient

问题描述

我正在尝试在 Codewars 网站上实现称为 Pairs of Pairs 的算法.我已经写了一个算法，但是它不能通过所有测试，并且需要很多时间来处理.请您建议我如何正确有效地解决它.谢谢！

I'm trying to implement algorithm called Sum of Pairs on Codewars website. I have written an algorithm but it does not pass all tests and it takes a lot of time to process. Please can you suggest me how to solve it correctly and efficiently. Thanks!

以下说明

sum_pairs([11, 3, 7, 5],         10)
#              ^--^      3 + 7 = 10
== [3, 7]

sum_pairs([4, 3, 2, 3, 4],         6)
#          ^-----^         4 + 2 = 6, indices: 0, 2 *
#             ^-----^      3 + 3 = 6, indices: 1, 3
#                ^-----^   2 + 4 = 6, indices: 2, 4
#  * entire pair is earlier, and therefore is the correct answer
== [4, 2]

sum_pairs([0, 0, -2, 3], 2)
#  there are no pairs of values that can be added to produce 2.
== None/nil/undefined (Based on the language)

sum_pairs([10, 5, 2, 3, 7, 5],         10)
#              ^-----------^   5 + 5 = 10, indices: 1, 5
#                    ^--^      3 + 7 = 10, indices: 3, 4 *
#  * entire pair is earlier, and therefore is the correct answer
== [3, 7]

我的代码是:

var sum_pairs=function(ints, s){
    var total = 0;
    var list = [];
    for (var i=0; i < ints.length; i++) {
      for (var j=1; j < ints.length; j++) {
          total = ints[i]+ints[j];
          if (total === s) {
            list.push(ints[i], ints[j]); 
            return list;
        }  
        //console.log(total);
      }
    }
}

sum_pairs([1,2,3,4,1,0], 2);

它没有通过此测试:

✘ First Match From Left REDUX!: [10,5,2,3,7,5] should return [3, 7] for sum = 10

推荐答案

如果期望包含10M个元素的数组，则不能使用O(N ^ 2)算法.下面的代码怎么样:

You can not use O(N^2) algorithms if you expect arrays of 10M elements. How about code below:

var sum_pairs=function(ints, s, und){
    var h = {}
    for(var i=ints.length - 1; i >= 0; --i){
      h[ints[i]] = i
    }
    for(var i=0; i < ints.length; ++i){
      var ci = ints[i]
      var e = h[s - ci]
      if(e < i){
        return [s - ci, ci]
      }
    }
    return und
}

这篇关于我的算法有点过时，效率极低的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！