我们的工作是编写一个最多在线性时间内解决两和问题的函数。
给定一个整数数组,我们必须找到两个数字,以便它们加起来成为一个特定的目标数字。
函数twoSum应该返回加到目标上的两个数字的索引,如果没有两个元素加到目标上,则我们的函数应该返回一个空数组。
我们将使用哈希映射来记录已经出现的项目,每次通过时,我们都会检查映射中是否存在任何元素,将其添加到当前元素中时,这些元素将累加到目标中,如果存在则返回一个包含其索引的数组,如果我们不满足此条件而经过整个循环,则将返回一个空数组。
const arr = [2, 5, 7, 8, 1, 3, 6, 9, 4]; const sum = 10; const twoSum = (arr, sum) => { const map = {}; for(let i = 0; i < arr.length; i++){ const el = sum - arr[i]; if(map[el]){ return [map[el], i]; }; map[arr[i]] = i; }; return []; }; console.log(twoSum(arr, sum)); console.log(twoSum(arr, 12)); console.log(twoSum(arr, 13)); console.log(twoSum(arr, 14)); console.log(twoSum(arr, 24));
输出结果
控制台中的输出将为-
[ 2, 5 ] [ 1, 2 ] [ 1, 3 ] [ 3, 6 ] []