给定一个包含数字的数组，如何编写一个递归函数来查找数组中哪些索引的两个元素相加等于目标值？

Question

题目要求：给定一个整数数组，返回两个数字的下标，使它们相加等于特定的目标值。

你可以假设每个输入都只有一个解决方案。

例如：给定 nums = [2, 11, 15, 7]，目标值 target = 9，

因为 nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0，1]。

这里是我的解决方案，但它似乎没有给出我期望的输出：

var sumTarget = function(array, target) {
  var result = [];
  var copy = array.slice();
  var firstValue = array.shift();
  if (array.length === 0) {
    return result;
  }
  for (var i = copy.indexOf(firstValue) + 1; i < copy.length; i++) {
    if (firstValue + copy[i] === target) {
      Array.prototype.push.apply(result, [copy.indexOf(firstValue), i]);
    }
  }

  return sumTarget(array, target);
};

- Derek Hoang

---

你的意思是它应该返回 [0, 3] 吗？或者更准确地说，是 [[0, 3]]。 - nonopolarity

Answer 1

类似这样：

https://jsfiddle.net/rqp93gpy/2/

（注：此处为原文内容，无需翻译）

function getIndexes(arr, target, offset) {
  var result = [], i;
  if (arr.length <= 1) return [];

  if (offset === undefined) offset = 0;

  for (i = 1; i < arr.length; i++) {
    if (arr[0] + arr[i] === target) {
      result.push([offset, offset + i]);
    }
  }
  return result.concat(getIndexes(arr.slice(1), target, offset + 1));
}

console.log(JSON.stringify(getIndexes([2, 11, 15, 7, 6, 3, 4, 8, 9, 5, 7], 9),
                           null, 4));

输出：

[
    [
        0,
        3
    ],
    [
        0,
        10
    ],
    [
        4,
        5
    ],
    [
        6,
        9
    ]
]

- nonopolarity

Answer 2

虽然另一个基于递归方法的答案看起来更整洁，但它的算法是暴力的，自然而然地在性能上会稍微低效一些。这种方法更加实用，结果在repl.it上快1.5倍，在Opera上快2.5倍，在Firefox上快8倍，在Chrome控制台测试中快25倍。

大致逻辑如下：

1. 过滤出大于目标值的项
2. 通过建立两个独立的哈希表对象（LUT），将奇数和偶数数组项分开，其中我们将有效的数组项作为属性的唯一副本，并且每个属性都有一个索引数组。
3. 根据目标值是奇数还是偶数执行两个不同的算法

让我们看看；

var arr = [4,6,12,5,8,4,3,9,19,5,21,13,8,15,7,23,6,11,10,15,1,12,19,31,14,6,3,16],
    tar = 12;

function getIndexes(arr, target){
var   odds = {},
     evens = {},
   results = [],
makeResult = (a,b) => !!b ? a.forEach( e => b.forEach( f => results.push([e,f])))
                          : a.reduce((p,c,i) => {makeResult([p],a.slice(i)); return c});
arr.forEach((e,i) => e < target ? e%2 == 1 ?  !!odds[e] ?  odds[e].push(i) : ( odds[e] = [],  odds[e].push(i))
                                           : !!evens[e] ? evens[e].push(i) : (evens[e] = [], evens[e].push(i))
                                : false);
var oko = Object.keys(odds),
    oke = Object.keys(evens);
target%2 == 1 ? oko.length <= oke.length ? oko.forEach( e => evens[target-e] && makeResult( odds[e], evens[target-e]))
                                         : oke.forEach( e =>  odds[target-e] && makeResult(evens[e],  odds[target-e]))
              : (oko.forEach( e => (e <= target/2 &&  odds[target-e]) && (e < target/2 ? makeResult( odds[e],  odds[target-e])
                                                                                       : makeResult( odds[e]))),
                 oke.forEach( e => (e <= target/2 && evens[target-e]) && (e < target/2 ? makeResult(evens[e], evens[target-e])
                                                                                       : makeResult(evens[e]))));
return results;
}
document.write('<pre>' + JSON.stringify(getIndexes(arr, tar), 0, 2) + '</pre>');

对于那些喜欢递归的人，makeResults函数中有一小部分递归。

性能比较方面，您可以查看https://repl.it/CIxd/1 vs https://repl.it/CIxr

- Redu

---

你需要奇数和偶数吗？你不能只是构建一个哈希表（字典），将数字映射到原始索引，然后说，如果目标是9，那么当你看到4时，检查5是否存在，如果是，则这是一个答案。这是平均情况下的O(n)。因此，在目标为10且有许多5的情况下，所有这些都可以是答案...我想最坏的情况可能是O(n^2)，当你有一个包含一百万个5的数组，并且目标是10时...但是如果答案集中有大约（n ^ 2/2）个项目，那么下限（最小步骤）不管怎样都需要是O(n ^ 2)。 - nonopolarity

我构建了两个哈希表，一个用于奇数，一个用于偶数。它们都包含每个数字的唯一表示及其每次出现的索引。因此，如果数字4在数组中出现3次，索引分别为5、15和17，则偶数哈希表看起来像{4：[5,15,17]}等等...必须将奇数和偶数分开，因为根据目标是奇数还是偶数，算法会有所不同。对于偶数目标，我们将在哈希表内部检查两个哈希表，直到目标数字的一半。 - Redu

因此，如果目标是12，而偶数包含[2、4、6、8、10]，则我们不需要检查8和10，因为当我们检查2和4时已经检查过它们了。而我们将检查6的多个出现。如果目标是奇数，则意味着它是一个奇数和偶数之和。所以这次我们将取奇数或偶数哈希表中较短的一个，并在其上应用forEach。我想要提高效率的一件事是将所有数组函数转换为它们传统的for循环等效函数，或者使用lodash进行适应。这将引入约300％的性能增长。 - Redu

Answer 3

投票给这个:

    function sumTarget(ar, t) {
        var res = [];
        for (var i = 0, n = ar.length; i < n-1; i++) {
            for (var j = i + 1; j < n; j++) {
                if (ar[i] + ar[j] == t) {
                    res.push({ num1: i, val1: ar[i], num2: j, val2: ar[j] });
                }
            }
        }
        console.log(JSON.stringify(res));
    }
    sumTarget([2, 11, 15, 7], 9);

希望它能对你的课程有所帮助；）

- Alex Kudryashev

---

我认为这个问题需要使用递归吗？ - nonopolarity