hasPairsWithSum谷歌面试问题
hasPairsWithSum谷歌面试问题
提问于 2021-10-03 13:33:28
我通过迭代数组解决了这个问题，然后在和等于array[i] + item时找到项，返回true，否则返回false。
，我的问题是，，=>，我怎样才能返回这些数字的指数，它们的加起来不仅是真的？使用下面相同的代码：
function hasPairsWithSum(array,sum) {
for (let i = 0; i < array.length; i++) {
if (array.find((item) => {return sum === array[i] + item}
));
return true;
};
return false;
};
console.log(hasPairsWithSum([1,2,4,4],8))注意:时间复杂度必须小于O(n ^ 2)。
回答 4
Stack Overflow用户
发布于 2021-10-03 18:08:14
JavaScript O(n)溶液
function hasPairsWithSum(array, sum) {
const map = new Map ();
for(let i = 0; i < array.length; i++) {
let currVal = array[i];
if (map.has(currVal)) {
return [map.get(currVal),i]
}
// difference value = sum - current value
let diff = sum - currVal
map.set(diff,i)
}
};
console.log(hasPairsWithSum([2,2,4,4], 8))Stack Overflow用户
发布于 2021-10-03 13:37:29
请参考这段代码。
function hasPairsWithSum(array,sum) {
let result = [];
for (let i = 0; i < array.length; i++) {
if (array.some((item, index) => {return i === index ? false : sum === array[i] + item}))
result.push(i);
};
return result;
};
console.log(hasPairsWithSum([1,2,4,4],8))
console.log(hasPairsWithSum([3,2,4],6))
console.log(hasPairsWithSum([0,4,3,0],0))
Stack Overflow用户
发布于 2021-10-03 14:44:17
您必须迭代数组元素，在每次迭代时检查数组的每个元素(除了最后一个)，它右边的所有元素如下所示：
function findIndexes(array, sum) {
const result = [];
for (let i = 0; i < array.length -1; ++i) {
for (let j = i + 1; j < array.length; ++j) {
if ((array[i] + array[j]) === sum) {
result.push([i, j]);
}
}
}
return result;
}
console.log(findIndexes([1, 2, 4, 4], 8));
console.log(findIndexes([3, 2, 4], 6));
更新：
可以使用一个辅助Map结构来获得线性O(n)复杂度，该结构将整数值作为键与包含数组中元素的所有索引的列表作为值相关联，如下所示：
function findIndexes(array, sum) {
const map = new Map();
const result = [];
for (let i = 0; i < array.length; ++i) {
const a = array[i];
const b = sum - a;
if (map.has(b)) {
for (const index of map.get(b)) {
result.push([index, i]);
}
}
const l = map.has(a) ? map.get(a) : [];
l.push(i);
map.set(a, l);
}
return result;
}
console.log(findIndexes([1, 2, 4, 4], 8));
console.log(findIndexes([3, 2, 4], 6));
console.log(findIndexes([1, 1, 1], 2));
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/69425321
复制相关文章
相似问题
腾讯云开发者
