找到数组中和为固定值的元素

假设一个数组为[1, 1, 2, 3, 2, 0]，要求出其中两两相加和为3的所有元素，该如何操作？

第一种：暴力循环

var arr = [1, 1, 2, 3, 2, 0];
var target = 3;

for (var i = 0; i < arr.length - 1; i++) {
    for (var j = i + 1; j < arr.length; j++) {
        if (arr[i] + arr[j] === target) {
            console.log(arr[i] + ', ' + arr[j]);
        }
    }
}

第二种：先排序再比较

如果两数之和大于target，则需要减小其中较大的数，反之要增加较小的数。因为数组中存在重复元素，所以在每次寻找到匹配元素后，试探左右游标的下一个元素是否满足要求，来避免漏掉重复元素。

var arr = [1, 1, 2, 3, 2, 0];
var target = 3;
var left = 0;
var right = arr.length - 1;

arr.sort();
console.log(arr);

while (left < right) {
    if (arr[left] + arr[right] === target) {
        console.log(arr[left] + ', ' + arr[right]);

        // 额外的判断来解决数组的重复数字问题
        if (arr[left + 1] + arr[right] === target) {
            console.log(arr[left + 1] + ', ' + arr[right]);
            right--;
            continue;
        }
        if (arr[left] + arr[right - 1] === target) {
            console.log(arr[left] + ', ' + arr[right - 1]);
            left++;
            continue;
        }

        left++;
        right--;

    } else if (arr[left] + arr[right] < target) {
        left++;
    } else {
        right--;
    }
}

第三种：哈希表保存满足条件的数字与其出现次数

JavaScript中，对象属性的实现就是哈希表，因此用对象来存储数组迭代过程中满足条件的数字，为了不漏掉重复元素，同时也统计了满足条件的数字出现的次数。

var arr = [1, 1, 2, 3, 2, 0];
var target = 3;
var lookUp = {};

arr.forEach(function(value) {
    var tempValue = target - value;
    if (tempValue in lookUp) {
        for (var i = 0; i < lookUp[tempValue]; i++) {
            console.log(value + ', ' + tempValue);
        }
    } else {
        lookUp[value] ? lookUp[value]++ : lookUp[value] = 1;
    }
})
Some rights reserved
Except where otherwise noted, content on this page is licensed under a Creative Commons Attribution 4.0 International license