Simple Note

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

2016.02.28

假设一个数组为[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;
    }
})
Comments
Write a Comment