JavaScript 以线性时间解决Two sum问题

问题陈述要求在JavaScript中使用线性时间执行Two sum问题。它定义和探索了各种算法，可以帮助我们找到在给定源数据中相互存在的最小公因数。

什么是JavaScript中的Two sum问题

在JavaScript中，Two sum问题等同于找到一个数值数组中的一对索引，使得它们的和等于用户提供的目标和。

给定一个整数数组和目标和，我们将遍历数组以找出一对数值，可能存在一对或多对数值的和等于给定输入源的目标值。一旦找到一对数值，我们可以查找它们的索引来解决整个问题陈述。

这里的一点小问题是，数组中的每个输入值只能使用一次，不能重复使用相同的元素进行求和，结果对可以以任何顺序返回。

示例

问题陈述的视觉示例如下：

const arr = [ 2 ,5 ,9 ,7 ,3 , 8 , 1 ];
const targetSum = 10 ;

输出

[ 0, 5 ] = arr[0] + arr[5]
[ 2, 6 ] = arr[2] + arr[6]
[ 3, 4 ] = arr[3] + arr[4]

这里我们通过扫描整个数组以编程方式匹配配对，将数组中的每个元素与数组中的其他不同元素进行比较，因为不允许选择或选定的特定元素重复出现在配对的成员之一中，这违反了已在问题陈述中提到的两个求和问题的规则。

方法1 – 使用循环

步骤1 ：声明一个名为twoSumProblem的函数，输入是一个数字数组，该数组将作为一个主要的输入源来找出满足目标和加上目标和值的索引对，这个目标和值也将由用户提供，因为要找出的索引对高度依赖于所需的和值。

步骤2 ：在给定的函数中，我们使用了嵌套循环功能，其中外部循环将选择索引对中的第一个数字，内部循环将选择索引对中的第二个值，这个值将以i循环的+1值向前移动，以跟踪和排列数据集域中的不同索引对。

步骤3 ：现在，索引对的排列将被传递给比较功能，以检查排列的特定对的加法是否满足目标和

步骤4 ：如果是的话，它将返回特定的索引作为元素的索引对，这些元素相加等于用户提供的targetSum。

示例

function twoSumProblem ( arr , targetSum )
{
   for(let i = 0; i<arr.length ; i++ )
   {
     for(let j = i+1 ; j<arr.length ; j++)
     {
       if(arr[i] + arr[j] === targetSum)
       {
         return [ i ,j ]
       }
     }
   }
}

const arr = [  2 ,5 ,9 ,7 ,3 , 8 ,1 ];
const pairOfIndices = twoSumProblem(arr , 10);
console.log(pairOfIndices);

输出

[ 0, 5 ]

时间和空间复杂度

在上述算法和代码中，我们使用了嵌套循环，其中外部循环将向前移动到数字数组的长度，导致O(n)的时间复杂度，而内部循环也向前移动到数组的长度，导致O(n)的时间复杂度。由于内部循环依赖于外部循环进行遍历，因此两个单独的时间复杂度的乘积结果为O(n) * O(n) = O(n^2)，即其最坏情况时间复杂度。

空间复杂度为O(1)，意味着空间复杂度是恒定的，因为我们没有分配任何额外的内存来解决该问题。

我们可以通过牺牲空间复杂度来进一步改进Two Sum问题的效率，将时间复杂度缩小。因为问题陈述中提到，要在线性时间内找到Two Sum问题的解决方案。

我们将使用HashMaps在Javascript中以线性时间解决Two Sum问题的时间复杂度和空间复杂度。

Javascript中的HashMaps是什么

Javascript中的HashMaps与数组的工作方式类似，在内部使用哈希函数将标签映射到数组索引或索引。它是一种类似于数组的数据结构，HashMap具有使用键和值对的哈希表，其中哈希的键指的是数组中的索引。

先前解决的算法由于嵌套循环功能而具有时间复杂度的最大缺陷，而哈希图可以遍历和查找任何内容或访问任何值的速度是O(1)的时间复杂度，这是最大的优势。

方法2

算法将循环遍历数组，并仅遍历一次数组中的每个元素，并且在目标和的过程中必须有一些内存辅助来存储您在中间位置得到的索引。这里的内存辅助工具是HashMap，其额外的内存分配丢弃了我们在adobe算法中使用的第二个嵌套循环，并使问题陈述能够在线性时间内解决。

第1步 : 声明一个名为newTwoSumProblem的函数，该函数接受数字数组和要查找一对索引的targetSum作为参数。

第2步 : 声明一个新的HashMap，并用空值进行初始化。

第3步 : 使用for循环遍历数组的长度，记住如果有任何其他数字可以添加到当前数字的currentValue中以达到目标和。

第4步 : 声明并赋值一个新的变量作为额外内存，如上所述，称为currentValue，它将在每次for循环迭代中接收i的当前值。

第5步 : 找到与当前值相关的一对索引的下一个值，使得新值基于剩余需要实现目标和的值的值使用哈希函数targetSum – currentValue进行计算。

第6步 : 使用哈希图函数寻找一对索引，其中当前值以键值对的模式存储，其中键是实际值本身，值是仅针对该值的特定索引。

第7步 ：如果哈希映射中没有找到当前值的配对，并且它等于undefined，则哈希映射将再次开始寻找其配对索引的补充，使用i的下一个值继续进行另一个数组的数字，并且重复相同的任务，直到找到满足目标和的索引配对。

示例

function newTwoSumProblem (arr, targetSum) {
  let hashMap = {};

  for(let i = 0; i < arr.length; i++) {

   const currentValue = arr[i];

   if(hashMap[targetSum - currentValue] !== undefined) 
   {
    return [hashMap[targetSum - currentValue], i];
   }

   hashMap[currentValue] = i;

  }
  return [];
}

const arr = [  2 ,7 , 11, 15 ];
const pairOfIndices = newTwoSumProblem(arr , 9);
console.log(pairOfIndices);

以后我们还可以使用上面的主要代码调用该函数，控制台的输出将如下所示：