JavaScript 中线性时间复杂度的两数之和问题

---

问题陈述要求在 JavaScript 中以线性时间执行两数之和问题。它定义并探讨了各种算法，这些算法可以帮助我们在 JavaScript 中给定的源数据中找到存在的最小公因数。

什么是 JavaScript 中的两数之和问题？

JavaScript 中的两数之和问题等同于找到给定输入数字数组中的一对索引，该索引加起来等于目标和，目标和也由用户作为输入提供。

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

这里的小技巧是数组中的每个输入值只能使用一次，并且您不能重复使用相同的元素进行求和，其中结果对可以按任意顺序返回。

示例

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

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：声明一个名为 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)，这意味着空间复杂度是恒定的，因为我们没有分配任何额外的内存来解决问题。

我们可以以一种更有效的方式进一步优化 twoSumProblem，以牺牲空间复杂度为代价来降低时间复杂度。因为正如问题陈述中提到的，要在线性时间内找到两数之和问题。

我们将使用哈希表在 JavaScript 中以线性时间和空间复杂度来解决两数之和问题。

什么是 JavaScript 中的哈希表？

JavaScript 中的哈希表在幕后就像数组一样工作，它使用哈希函数将标签映射到数组索引或索引。它是一种类似于数组的数据结构，哈希表具有使用键值对的哈希表，其中哈希键指的是数组中的索引。

先前解决的算法由于嵌套循环功能而导致时间复杂度最大，而哈希表可以遍历并找到任何内容，或者任何值的访问速度为 O(1) 时间复杂度，这是最大的优势。

算法

该算法将制定策略来循环数组并仅遍历数组中存在的每个元素一次，并且必须有一些内存帮助来存储在朝着目标和值的过程中获得的索引。这里的内存帮助器是哈希表，其额外的内存分配丢弃了我们在 adobe 算法中使用的第二个嵌套循环，并允许问题陈述在线性时间内解决。

步骤 1：声明一个名为 newTwoSumProblem 的函数，该函数接收数字数组和您要查找索引对的目标和。

步骤 2：声明一个新的哈希表，并初始化为空值。

步骤 3：使用 for 循环遍历数组的长度，直到数组的长度，并牢记是否有任何其他数字可以加到数字的当前值以实现目标和。

步骤 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);

稍后我们还可以使用上述主代码调用该函数，控制台中的输出将是

输出

[0 , 1 ] 

以下代码是人们在查看问题陈述以获得更好的空间和时间质量时可以想到的有效且优化的前向代码。

在上面的代码中，我们声明了一个接收数组输入的函数。然后我们一步一步地进行，首先关注问题陈述的主要内容，即在数字数组中找到任何其他数字，该数字可以加到当前数字以等于目标和值。

通过这种方式，我们可以从初始索引 0 开始循环，并尝试查找其他数字值，该值是通过使用 targetSum-currentValue 在哈希表中查找获得的，如果它找不到当前值，则将当前值存储在哈希表中，使用键值对结构和 for 循环向前移动到索引值 1，并重复相同的过程，直到它找到满足目标和的互补索引对。

时间和空间复杂度

这是一种有效的算法，现在使用哈希表，时间复杂度为 O(n)，空间复杂度也为 O(n)。因此它在线性时间内解决了问题陈述。

结论

这就是我们如何在编码环境中逻辑上和有效地解决上述问题陈述的方式，将代码从嵌套循环更改为哈希表功能，这使我们拥有巨大的能力来遍历和执行操作，并在恒定的时间和空间复杂度内使用它。