JavaScript 中线性时间的二和问题
问题陈述说在 JavaScript 中以线性时间执行二和问题。它定义并探索了各种算法，这些算法可以帮助我们根据 JavaScript 中给定的源数据找到相互存在的最小公因子。
JavaScript 中的二和问题是什么?
JavScript 中的二和问题等于在作为输入给出的数字数组中找到一对索引，这些索引加起来等于目标和，该目标和也是由用户提供的输入。
给定一个整数数组和目标和，我们将遍历数字数组以找出数字对，可能有一对或多对数字加起来等于作为输入源给出的目标值。一旦找到这对数字，我们就可以寻找它们的索引来整体解决整个问题陈述。
这里的小问题是，数字数组中的每个输入值只能使用一次，并且不能两次使用同一个元素进行求和，其中结果对可以按任何顺序返回。
示例
问题陈述的可视化示例如下:
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:在给定的函数中，我们使用了嵌套循环功能，其中外部循环将挑选出索引对中的第一个数字，内部循环将从索引对中挑选出第二个值，该索引对将向前移动 + 1 个 i 循环的值以跟踪和排列数据集域中的不同索引对。
步骤 3:现在将对索引对数量的排列进行比较功能，以检查排列的特定对的添加是否足以达到目标总和
步骤 4:如果是，它将返回特定索引作为元素索引对，这些元素的索引加起来等于由用户。
示例
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，以牺牲空间复杂度为代价来降低时间复杂度。因为正如问题陈述中提到的那样，要在线性时间内找到两个和问题。
我们将使用 HashMaps 以线性时间和空间复杂度解决 Javascript 中的二和问题。
JavaScript 中的 HashMaps 是什么?
JavScript 中的 HashMaps 就像后台的数组一样工作，它使用哈希函数将标签映射到数组索引或索引。它是一种类似于数组的数据结构，哈希图具有使用键和值对的哈希表，其中哈希键引用数组中的索引。
之前解决的算法由于嵌套循环功能而具有时间复杂度的最大缺点，其中哈希图可以遍历并找到任何东西或访问任何值的速度是 O(1) 时间复杂度，这是最大的优势。
算法
该算法将制定策略来循环数组并仅遍历数组中存在的每个元素一次，并且必须有一些内存帮助来存储在瞄准 targetSum 值时中途获得的索引。这里的内存助手是 hashmap，它的额外内存分配会丢弃我们在 adobe 算法中使用的第二个嵌套循环，并允许在线性时间内解决问题陈述。
步骤 1 :声明一个名为 newTwoSumProblem 的函数，该函数接受数字数组和您想要为其找到一对索引的 targetSum。
步骤 2 :声明一个新的 hashMap，用空值初始化。
步骤 3:使用 for 循环遍历数组的长度，直到达到数组的长度，同时记住是否有任何其他数字可以加到数字的 currentValue 以达到目标总和。
步骤 4 :声明并分配一个新变量作为额外内存，如上所述，称为 currentValue，它将在 for 循环的每次迭代中接受 i 的当前值
步骤 5 :根据当前值找到一对索引的下一个值，这样新值将根据使用 targetSum - currentValue 哈希函数实现目标总和所需的剩余值来计算。
步骤 6:使用哈希映射函数查找索引对，其中当前值存储在键和值对模式中，其中键是实际值本身，值是仅用于该值的特定索引。
步骤 7:如果在 hashmap 中未找到当前值的对并且它等于 undefined ，则 hashmap 将再次开始查找其互补索引对，下一个值为 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)。因此，它在线性时间内解决了问题陈述。
结论
这就是我们如何在编码上下文中逻辑高效地思考上述问题陈述，将代码从嵌套循环转换为哈希图功能，这使我们能够在恒定的时间和空间复杂度内使用它来遍历和执行操作。
