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