JavaScript 中的二和问题

总体思路

二和问题是一个经典的算法问题。它要求您在数组中查找两个数字，它们的总和达到所提供的特定 * 目标 *，然后从给定数组中返回它们的索引。

问题陈述

给定一个整数数组 nums 和一个整数目标，返回两个数字的索引，使它们相加等于目标。每个输入都只有一个解决方案，并且您不能两次使用相同的元素。

输入：nums = [2, 7, 11, 15]，目标 = 9
输出：[0, 1]
解释： nums[0] nums[1] = 2 7 = 9

方法1 暴力破解

解决任何问题的第一个方法可能就是完成某件事，并且是概念上最简单的事情。

用两个循环迭代数组并检查所有数字对。

const twoSum = (nums, target) => {
  for(let i = 0; i 



<h3>
  
  
  方法 1 复杂性
</h3>

<p><strong>时间复杂度</strong>为<em>O(n²)</em></p>

<ol>
<li>嵌套循环检查每对数字</li>
<li>检查每种可能的组合</li>
<li>使用大数组时变得非常慢</li>
</ol>

<p><strong>空间复杂度</strong>为<em>O(1)</em><br>
1.我们没有创建新的数据结构</p>
<h2>
  
  
  方法 2 更高效，这就是我们想要的。
</h2>

<p>我们将使用哈希映射来解决这个问题。让我们稍微解释一下这个算法</p>

<ol>
<li>我们使用哈希映射（JavaScript 中的对象）来存储我们看到的数字</li>
<li>对于每个数字，我们计算其补码（目标 - 当前数字）</li>
<li>我们检查补集是否存在于我们的地图中</li>
<li>如果是，我们就找到了两个数字并返回它们的索引</li>
<li>如果没有，我们将当前号码添加到地图</li>
</ol>

<p>所以第一个解决方案可能是使用常规 JS 对象并以这种方式构建我们的 HashMap<br>
</p>

<pre class="brush:php;toolbar:false">const twoSumOptimizedRegularObject = (nums, target) => {
  const objectStuff = {}

  // write a for loop, to go through the arr
  for (let i = 0; i 



<p>第二种解决方案实际上是在 JS 中使用 Map 数据结构。这允许更严格、更健壮的实现，使用 Map 对象（在 ES6 中引入）并且通常是首选。 Map 提供显式哈希映射行为，并避免 JavaScript 对象的一些怪癖，例如从 Object.prototype 继承属性。<br>
</p>

<pre class="brush:php;toolbar:false">const twoSumOptimized = (nums, target) => {
  const mapOfStuff = new Map()

  // write a for loop, to go through the arr
  for (let i = 0; i 



<h3>
  
  
  方法 2 复杂性
</h3>

<p><strong>时间复杂度</strong>为<em>O(n)</em></p>

<ol>
<li>单次遍历数组</li>
<li>哈希映射提供 O(1) 查找</li>
<li>总时间与数组大小成线性关系</li>
</ol>

<p><strong>空间复杂度</strong> 为 O(n)<br>
在最坏的情况下，我们可能会存储几乎所有数字<br>
时间和内存效率之间的权衡</p>

<h2>
  
  
  注意事项
</h2>

<ol>
<li>空数组</li>
<li>不存在解决方案</li>
<li>有多种解决方案。在这种情况下，询问您是否在第一次迭代后返回。</li>
</ol>


          

            
        

以上是JavaScript 中的二和问题的详细内容。更多信息请关注PHP中文网其他相关文章！