LeetCode 1：两数之和（Two Sum）
<h2 id="一题目描述">一、题目描述</h2><h3 id="原题">原题</h3>
<p>给定一个整数数组 <code>nums</code> 和一个整数目标值 <code>target</code>，请你在该数组中找出<strong>和为目标值</strong> <code>target</code> 的那<strong>两个</strong>整数，并返回它们的数组下标。</p>
<p>你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。</p>
<p>你可以按任意顺序返回答案。</p>
<h3 id="示例">示例</h3>
<pre><code>示例 1：
输入：nums = , target = 9
输出：
解释：因为 nums + nums == 9 ，返回
示例 2：
输入：nums = , target = 6
输出：
示例 3：
输入：nums = , target = 6
输出：
</code></pre>
<h3 id="约束条件">约束条件</h3>
<ul>
<li><code>2 <= nums.length <= 10⁴</code></li>
<li><code>-10⁹ <= nums <= 10⁹</code></li>
<li><code>-10⁹ <= target <= 10⁹</code></li>
<li><strong>只会存在一个有效答案</strong></li>
</ul>
<hr>
<h2 id="二题目解析">二、题目解析</h2>
<h3 id="核心问题拆解">核心问题拆解</h3>
<table>
<thead>
<tr>
<th>关键点</th>
<th>分析</th>
</tr>
</thead>
<tbody>
<tr>
<td><strong>输入</strong></td>
<td>整数数组 + 目标值</td>
</tr>
<tr>
<td><strong>输出</strong></td>
<td>两个数的<strong>下标</strong>（不是数值本身）</td>
</tr>
<tr>
<td><strong>约束</strong></td>
<td>同一元素不能使用两次</td>
</tr>
<tr>
<td><strong>保证</strong></td>
<td>有且仅有一个解</td>
</tr>
</tbody>
</table>
<h3 id="思考方向">思考方向</h3>
<div class="mermaid">flowchart LR
A[原问题] --> B["nums + nums = target"]
B --> C[转化思维]
C --> D["对于每个 nums<br/>寻找 target - nums"]
D --> E[如何快速查找?]
E --> F["哈希表 O(1)"]
</div><hr>
<h2 id="三算法解答">三、算法解答</h2>
<hr>
<h3 id="算法一暴力枚举法">算法一：暴力枚举法</h3>
<h4 id="1-算法原理描述">1. 算法原理描述</h4>
<p><strong>核心思想</strong>：穷举所有可能的两数组合，检查它们的和是否等于目标值。</p>
<p><strong>实现方式</strong>：</p>
<ul>
<li>使用两层循环</li>
<li>外层循环固定第一个数 <code>nums</code></li>
<li>内层循环遍历其后的所有数 <code>nums</code>（j > i）</li>
<li>检查 <code>nums + nums == target</code></li>
</ul>
<h4 id="2-算法解答过程">2. 算法解答过程</h4>
<p>以 <code>nums = </code>, <code>target = 9</code> 为例：</p>
<table>
<thead>
<tr>
<th>外层 i</th>
<th>内层 j</th>
<th>nums</th>
<th>nums</th>
<th>和</th>
<th>是否等于 target</th>
</tr>
</thead>
<tbody>
<tr>
<td>0</td>
<td>1</td>
<td>2</td>
<td>7</td>
<td>9</td>
<td>✅ 找到！</td>
</tr>
</tbody>
</table>
<p>返回 <code></code></p>
<h4 id="3-算法原理图像解析">3. 算法原理图像解析</h4>
<div class="mermaid">flowchart TD
subgraph 数组["数组 nums, target = 9"]
A0["=2"] --- A1["=7"] --- A2["=11"] --- A3["=15"]
end
subgraph 流程["暴力枚举流程"]
S[开始] --> L1["外层循环 i = 0"]
L1 --> L2["内层循环 j = 1"]
L2 --> C1{"nums + nums<br/>= 2 + 7 = 9<br/>== target?"}
C1 -->|"✅ 是"| R["返回 "]
C1 -->|"❌ 否"| L3["j++, 继续内层"]
L3 --> L4["若内层结束<br/>i++, 继续外层"]
end
subgraph 复杂度["复杂度分析"]
T["⏱ 时间: O(n²)"]
SP["💾 空间: O(1)"]
end
</div><h4 id="4-算法代码">4. 算法代码</h4>
<pre><code class="language-cpp">class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
// 外层循环：固定第一个数
for (int i = 0; i < n - 1; i++) {
// 内层循环：遍历第一个数之后的所有数
for (int j = i + 1; j < n; j++) {
// 检查两数之和是否等于目标值
if (nums + nums == target) {
return {i, j};
}
}
}
// 题目保证有解，这里不会执行到
return {};
}
};
</code></pre>
<h4 id="5-复杂度分析">5. 复杂度分析</h4>
<table>
<thead>
<tr>
<th>复杂度类型</th>
<th>值</th>
<th>说明</th>
</tr>
</thead>
<tbody>
<tr>
<td>时间复杂度</td>
<td>O(n²)</td>
<td>两层嵌套循环，最坏情况遍历 n(n-1)/2 次</td>
</tr>
<tr>
<td>空间复杂度</td>
<td>O(1)</td>
<td>只使用常数额外空间</td>
</tr>
</tbody>
</table>
<h4 id="6-使用范围">6. 使用范围</h4>
<table>
<thead>
<tr>
<th>场景</th>
<th>适用性</th>
</tr>
</thead>
<tbody>
<tr>
<td>数据规模小（n < 1000）</td>
<td>✅ 适用</td>
</tr>
<tr>
<td>数据规模大</td>
<td>❌ 会超时</td>
</tr>
<tr>
<td>对空间要求极高</td>
<td>✅ 适用</td>
</tr>
<tr>
<td>面试中作为初始解法</td>
<td>✅ 适用，但需优化</td>
</tr>
</tbody>
</table>
<hr>
<h3 id="算法二哈希表法一遍哈希-最优解">算法二：哈希表法（一遍哈希）⭐ 最优解</h3>
<h4 id="1-算法原理描述-1">1. 算法原理描述</h4>
<p><strong>核心思想</strong>：将「寻找两数之和」转化为「寻找差值」问题。</p>
<p><strong>关键转换</strong>：</p>
<pre><code>nums + nums = target
↓ 转化
nums = target - nums
</code></pre>
<p><strong>实现方式</strong>：</p>
<ul>
<li>使用哈希表存储<strong>已遍历过的元素</strong>及其下标</li>
<li>对于当前元素 <code>nums</code>，计算 <code>complement = target - nums</code></li>
<li>在哈希表中查找 <code>complement</code> 是否存在</li>
<li>若存在，说明找到答案；若不存在，将当前元素加入哈希表</li>
</ul>
<p><strong>优势</strong>：哈希表的查找时间复杂度为 O(1)，整体只需一次遍历。</p>
<h4 id="2-算法解答过程-1">2. 算法解答过程</h4>
<p>以 <code>nums = </code>, <code>target = 9</code> 为例：</p>
<table>
<thead>
<tr>
<th>步骤</th>
<th>当前元素</th>
<th>complement</th>
<th>哈希表查找</th>
<th>操作</th>
<th>哈希表状态</th>
</tr>
</thead>
<tbody>
<tr 2:0="">
<td>1</td>
<td>nums=2</td>
<td>9-2=7</td>
<td>7 不存在</td>
<td 2:0="">存入</td>
<td></td>
</tr>
<tr>
<td>2</td>
<td>nums=7</td>
<td>9-7=2</td>
<td>2 存在！下标0</td>
<td>返回 </td>
<td>-</td>
</tr>
</tbody>
</table>
<h4 id="3-算法原理图像解析-1">3. 算法原理图像解析</h4>
<div class="mermaid">flowchart TD
subgraph 输入["输入: nums = , target = 9"]
direction LR
N0["2"] --> N1["7"] --> N2["11"] --> N3["15"]
end
subgraph Step1["步骤1: 处理 nums = 2"]
S1A["计算 complement = 9 - 2 = 7"]
S1B{"哈希表中<br/>查找 7"}
S1C["❌ 未找到"]
S1D["存入哈希表<br/>{2: 0}"]
S1A --> S1B --> S1C --> S1D
end
subgraph Step2["步骤2: 处理 nums = 7"]
S2A["计算 complement = 9 - 7 = 2"]
S2B{"哈希表中<br/>查找 2"}
S2C["✅ 找到! 下标=0"]
S2D["返回 "]
S2A --> S2B --> S2C --> S2D
end
输入 --> Step1 --> Step2
subgraph 要点["🔑 核心要点"]
K1["边遍历边建表"]
K2["先查找再存入"]
K3["O(1) 查找"]
end
</div><p><strong>哈希表状态变化：</strong></p>
<div class="mermaid">flowchart LR
subgraph T1["初始状态"]
E1["空 ∅"]
end
subgraph T2["处理2后"]
H1["2 → 0"]
end
subgraph T3["处理7时"]
H2["2 → 0"]
F["查找2 ✅"]
end
T1 -->|"存入 2:0"| T2 -->|"查找2"| T3
</div><h4 id="4-算法代码-1">4. 算法代码</h4>
<pre><code class="language-cpp">class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// 哈希表：key = 数值，value = 下标
unordered_map<int, int> hashMap;
for (int i = 0; i < nums.size(); i++) {
// 计算当前元素的"配对值"
int complement = target - nums;
// 在哈希表中查找配对值
if (hashMap.find(complement) != hashMap.end()) {
// 找到了！返回两个下标
return {hashMap, i};
}
// 未找到，将当前元素存入哈希表
hashMap] = i;
}
// 题目保证有解，这里不会执行到
return {};
}
};
</code></pre>
<h4 id="5-代码详解">5. 代码详解</h4>
<pre><code class="language-cpp">// 关键点解析：
// 1. 为什么用 unordered_map 而不是 map？
// - unordered_map 基于哈希表，查找/插入 O(1)
// - map 基于红黑树，查找/插入 O(log n)
// 2. 为什么先查找再存入？
// - 避免同一元素被使用两次
// - 例如：nums = , target = 6
// - 第一个3存入后，第二个3能找到第一个3
// 3. hashMap.find() vs hashMap.count()
// - find() 返回迭代器，未找到返回 end()
// - count() 返回 0 或 1
// - 两种写法都可以，find() 更常用
</code></pre>
<h4 id="6-复杂度分析">6. 复杂度分析</h4>
<table>
<thead>
<tr>
<th>复杂度类型</th>
<th>值</th>
<th>说明</th>
</tr>
</thead>
<tbody>
<tr>
<td>时间复杂度</td>
<td>O(n)</td>
<td>只需遍历数组一次，哈希表操作 O(1)</td>
</tr>
<tr>
<td>空间复杂度</td>
<td>O(n)</td>
<td>最坏情况需存储 n-1 个元素</td>
</tr>
</tbody>
</table>
<h4 id="7-使用范围">7. 使用范围</h4>
<table>
<thead>
<tr>
<th>场景</th>
<th>适用性</th>
</tr>
</thead>
<tbody>
<tr>
<td>数据规模大</td>
<td>✅ 最优解</td>
</tr>
<tr>
<td>需要快速查找</td>
<td>✅ O(1) 查找</td>
</tr>
<tr>
<td>对空间敏感</td>
<td>⚠️ 需要额外空间</td>
</tr>
<tr>
<td>需要返回下标</td>
<td>✅ 适用</td>
</tr>
<tr>
<td>数组无序</td>
<td>✅ 适用</td>
</tr>
</tbody>
</table>
<hr>
<h3 id="算法三排序--双指针法特殊场景">算法三：排序 + 双指针法（特殊场景）</h3>
<blockquote>
<p>⚠️ <strong>注意</strong>：此方法会丢失原始下标，需要额外处理。仅适用于<strong>返回值而非下标</strong>的变体题目。</p>
</blockquote>
<h4 id="1-算法原理描述-2">1. 算法原理描述</h4>
<p><strong>核心思想</strong>：利用有序数组的性质，使用双指针从两端向中间逼近。</p>
<p><strong>实现方式</strong>：</p>
<ol>
<li>将数组排序</li>
<li>设置左指针 <code>left = 0</code>，右指针 <code>right = n-1</code></li>
<li>计算 <code>sum = nums + nums</code>
<ul>
<li>若 <code>sum == target</code>：找到答案</li>
<li>若 <code>sum < target</code>：左指针右移（增大和）</li>
<li>若 <code>sum > target</code>：右指针左移（减小和）</li>
</ul>
</li>
</ol>
<h4 id="2-算法解答过程-2">2. 算法解答过程</h4>
<p>以 <code>nums = </code>, <code>target = 9</code> 为例（已排序）：</p>
<table>
<thead>
<tr>
<th>步骤</th>
<th>left</th>
<th>right</th>
<th>nums</th>
<th>nums</th>
<th>sum</th>
<th>与target比较</th>
<th>操作</th>
</tr>
</thead>
<tbody>
<tr>
<td>1</td>
<td>0</td>
<td>3</td>
<td>2</td>
<td>15</td>
<td>17</td>
<td>17 > 9</td>
<td>right--</td>
</tr>
<tr>
<td>2</td>
<td>0</td>
<td>2</td>
<td>2</td>
<td>11</td>
<td>13</td>
<td>13 > 9</td>
<td>right--</td>
</tr>
<tr>
<td>3</td>
<td>0</td>
<td>1</td>
<td>2</td>
<td>7</td>
<td>9</td>
<td>9 == 9</td>
<td>✅ 找到</td>
</tr>
</tbody>
</table>
<h4 id="3-算法原理图像解析-2">3. 算法原理图像解析</h4>
<div class="mermaid">flowchart TD
subgraph 初始["排序后数组: , target = 9"]
direction LR
A["2"] --- B["7"] --- C["11"] --- D["15"]
end
subgraph R1["第1轮"]
R1L["L→2"]
R1R["15←R"]
R1C["2 + 15 = 17 > 9"]
R1A["R左移 ←"]
R1L --- R1R
R1C --> R1A
end
subgraph R2["第2轮"]
R2L["L→2"]
R2R["11←R"]
R2C["2 + 11 = 13 > 9"]
R2A["R左移 ←"]
R2L --- R2R
R2C --> R2A
end
subgraph R3["第3轮 ✅"]
R3L["L→2"]
R3R["7←R"]
R3C["2 + 7 = 9 == 9"]
R3A["找到答案!"]
R3L --- R3R
R3C --> R3A
end
初始 --> R1 --> R2 --> R3
</div><p><strong>双指针移动规则：</strong></p>
<div class="mermaid">flowchart TD
S["计算 sum = nums + nums"] --> C{sum 与 target 比较}
C -->|"sum == target"| F["✅ 找到答案"]
C -->|"sum < target"| L["L++ 需要更大的数"]
C -->|"sum > target"| R["R-- 需要更小的数"]
L --> S
R --> S
</div><h4 id="4-算法代码-2">4. 算法代码</h4>
<pre><code class="language-cpp">// 方法：保留原始下标的双指针解法
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// 创建副本并排序，保留原始下标
vector<pair<int, int>> numWithIndex;
for (int i = 0; i < nums.size(); i++) {
numWithIndex.push_back({nums, i});
}
sort(numWithIndex.begin(), numWithIndex.end());
int left = 0, right = nums.size() - 1;
while (left < right) {
int sum = numWithIndex.first + numWithIndex.first;
if (sum == target) {
return {numWithIndex.second, numWithIndex.second};
} else if (sum < target) {
left++;
} else {
right--;
}
}
return {};
}
};
</code></pre>
<h4 id="5-复杂度分析-1">5. 复杂度分析</h4>
<table>
<thead>
<tr>
<th>复杂度类型</th>
<th>值</th>
<th>说明</th>
</tr>
</thead>
<tbody>
<tr>
<td>时间复杂度</td>
<td>O(n log n)</td>
<td>排序 O(n log n) + 双指针 O(n)</td>
</tr>
<tr>
<td>空间复杂度</td>
<td>O(n)</td>
<td>需要存储原始下标</td>
</tr>
</tbody>
</table>
<h4 id="6-使用范围-1">6. 使用范围</h4>
<table>
<thead>
<tr>
<th>场景</th>
<th>适用性</th>
</tr>
</thead>
<tbody>
<tr>
<td>数组已排序</td>
<td>✅ 最佳选择</td>
</tr>
<tr>
<td>返回值而非下标</td>
<td>✅ 适用</td>
</tr>
<tr>
<td>需要返回下标</td>
<td>⚠️ 需额外处理</td>
</tr>
<tr>
<td>Two Sum II（有序数组）</td>
<td>✅ 标准解法</td>
</tr>
</tbody>
</table>
<hr>
<h2 id="四三种算法对比">四、三种算法对比</h2>
<div class="mermaid">flowchart LR
subgraph 暴力法["暴力枚举"]
B1["⏱ O n²"]
B2["💾 O 1"]
B3["⭐⭐"]
end
subgraph 哈希表["哈希表法 ✅推荐"]
H1["⏱ O n"]
H2["💾 O n"]
H3["⭐⭐⭐⭐⭐"]
end
subgraph 双指针["排序+双指针"]
D1["⏱ O n log n"]
D2["💾 O n"]
D3["⭐⭐⭐"]
end
暴力法 -->|"优化查找"| 哈希表
暴力法 -->|"有序场景"| 双指针
</div><table>
<thead>
<tr>
<th>算法</th>
<th>时间复杂度</th>
<th>空间复杂度</th>
<th>适用场景</th>
<th>推荐指数</th>
</tr>
</thead>
<tbody>
<tr>
<td>暴力枚举</td>
<td>O(n²)</td>
<td>O(1)</td>
<td>小数据、空间受限</td>
<td>⭐⭐</td>
</tr>
<tr>
<td><strong>哈希表法</strong></td>
<td><strong>O(n)</strong></td>
<td>O(n)</td>
<td><strong>通用最优解</strong></td>
<td>⭐⭐⭐⭐⭐</td>
</tr>
<tr>
<td>排序+双指针</td>
<td>O(n log n)</td>
<td>O(n)</td>
<td>有序数组、返回值</td>
<td>⭐⭐⭐</td>
</tr>
</tbody>
</table>
<h3 id="-面试建议">💡 面试建议</h3>
<div class="mermaid">flowchart LR
A["1️⃣ 先说暴力解法"] --> B["2️⃣ 分析瓶颈<br/>重复查找"]
B --> C["3️⃣ 引出哈希表优化"]
C --> D["4️⃣ 给出最优解"]
</div><hr>
<h2 id="五知识点总结">五、知识点总结</h2>
<h3 id="1-涉及的数据结构">1. 涉及的数据结构</h3>
<table>
<thead>
<tr>
<th>数据结构</th>
<th>用途</th>
<th>关键操作</th>
</tr>
</thead>
<tbody>
<tr>
<td>数组</td>
<td>存储原始数据</td>
<td>遍历 O(n)</td>
</tr>
<tr>
<td>哈希表</td>
<td>快速查找</td>
<td>查找/插入 O(1)</td>
</tr>
</tbody>
</table>
<h3 id="2-涉及的算法思想">2. 涉及的算法思想</h3>
<div class="mermaid">mindmap
root((两数之和<br/>核心思想))
暴力枚举
穷举所有可能
基础解法
空间换时间
用额外空间
降低时间复杂度
问题转化
找和转找差
核心优化思路
双指针
有序数组
两端逼近
</div><h3 id="3-c-知识点">3. C++ 知识点</h3>
<pre><code class="language-cpp">// 1. unordered_map 的使用
#include <unordered_map>
unordered_map<int, int> map;
map = value; // 插入
map.find(key); // 查找，返回迭代器
map.count(key); // 返回 0 或 1
map.end(); // 结束迭代器
// 2. vector 的初始化返回
return {a, b}; // 直接返回初始化列表
// 3. pair 的使用
pair<int, int> p = {value, index};
p.first; // 第一个元素
p.second; // 第二个元素
</code></pre>
<hr>
<h2 id="六做题模板">六、做题模板</h2>
<h3 id="两数之和类问题通用模板">「两数之和」类问题通用模板</h3>
<pre><code class="language-cpp">/*
* 两数之和问题模板
* 适用于：在数组中寻找满足 nums + nums = target 的配对
*/
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// Step 1: 创建哈希表
// key: 数组元素值
// value: 元素下标
unordered_map<int, int> hashMap;
// Step 2: 遍历数组
for (int i = 0; i < nums.size(); i++) {
// Step 3: 计算配对值
int complement = target - nums;
// Step 4: 在哈希表中查找配对值
if (hashMap.find(complement) != hashMap.end()) {
// 找到配对，返回结果
return {hashMap, i};
}
// Step 5: 将当前元素加入哈希表
hashMap] = i;
}
// Step 6: 未找到（题目保证有解时不会执行）
return {};
}
};
</code></pre>
<p><strong>模板流程图：</strong></p>
<div class="mermaid">flowchart TD
A[开始] --> B["创建空哈希表"]
B --> C["遍历数组 i = 0 to n-1"]
C --> D["计算 complement = target - nums"]
D --> E{"complement<br/>在哈希表中?"}
E -->|"是"| F["返回 hashMap, i"]
E -->|"否"| G["hashMap] = i"]
G --> H{"i < n-1?"}
H -->|"是"| C
H -->|"否"| I["返回空 无解"]
</div><h3 id="模板变体">模板变体</h3>
<h4 id="变体1返回所有配对">变体1：返回所有配对</h4>
<pre><code class="language-cpp">vector<vector<int>> twoSumAll(vector<int>& nums, int target) {
unordered_map<int, vector<int>> hashMap;// 存储所有下标
vector<vector<int>> result;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums;
if (hashMap.count(complement)) {
for (int j : hashMap) {
result.push_back({j, i});
}
}
hashMap].push_back(i);
}
return result;
}
</code></pre>
<h4 id="变体2有序数组双指针">变体2：有序数组（双指针）</h4>
<pre><code class="language-cpp">vector<int> twoSumSorted(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int sum = nums + nums;
if (sum == target) {
return {left, right};// 注意：这里返回的是下标
} else if (sum < target) {
left++;
} else {
right--;
}
}
return {};
}
</code></pre>
<hr>
<h2 id="七相关题目推荐">七、相关题目推荐</h2>
<div class="mermaid">flowchart TD
A["1. 两数之和"] --> B["167. 两数之和 II<br/>有序数组"]
A --> C["15. 三数之和"]
C --> D["18. 四数之和"]
A --> E["454. 四数相加 II"]
</div><table>
<thead>
<tr>
<th>题号</th>
<th>题目</th>
<th>难度</th>
<th>关联知识点</th>
</tr>
</thead>
<tbody>
<tr>
<td>167</td>
<td>两数之和 II - 输入有序数组</td>
<td>中等</td>
<td>双指针</td>
</tr>
<tr>
<td>15</td>
<td>三数之和</td>
<td>中等</td>
<td>双指针 + 去重</td>
</tr>
<tr>
<td>18</td>
<td>四数之和</td>
<td>中等</td>
<td>递归 + 双指针</td>
</tr>
<tr>
<td>454</td>
<td>四数相加 II</td>
<td>中等</td>
<td>哈希表分组</td>
</tr>
</tbody>
</table>
<hr>
<h2 id="八面试高频问答">八、面试高频问答</h2>
<h3 id="q1-为什么哈希表法要先查找再存入">Q1: 为什么哈希表法要先查找再存入？</h3>
<p><strong>答</strong>：为了避免同一元素被使用两次。例如 <code>nums = </code>, <code>target = 6</code>，如果先存入再查找，会错误地返回 <code></code>。</p>
<h3 id="q2-如果有多个答案怎么办">Q2: 如果有多个答案怎么办？</h3>
<p><strong>答</strong>：题目保证只有一个答案。若需返回所有答案，需要使用 <code>unordered_map<int, vector<int>></code> 存储所有下标。</p>
<h3 id="q3-哈希表-vs-红黑树map-vs-unordered_map">Q3: 哈希表 vs 红黑树（map vs unordered_map）？</h3>
<p><strong>答</strong>：</p>
<ul>
<li><code>unordered_map</code>：哈希表，查找 O(1)，无序</li>
<li><code>map</code>：红黑树，查找 O(log n)，有序</li>
</ul>
<p>本题不需要有序，选择 <code>unordered_map</code> 更优。</p>
<h3 id="q4-时间复杂度-on-是最优吗">Q4: 时间复杂度 O(n) 是最优吗？</h3>
<p><strong>答</strong>：是的。至少需要遍历一次数组才能确定答案，O(n) 是下界。</p>
<hr>
<h2 id="九一图总结">九、一图总结</h2>
<div class="mermaid">flowchart TB
subgraph 题目["📝 题目: 两数之和"]
Q["找两个数 和为target<br/>返回下标"]
end
subgraph 思路["💡 核心思路"]
T["找和转找差<br/>nums = target - nums"]
end
subgraph 解法["🔧 最优解法"]
S1["哈希表存储已遍历元素"]
S2["O 1 查找配对值"]
S3["边遍历边建表"]
end
subgraph 复杂度["⚡ 复杂度"]
C1["时间: O n"]
C2["空间: O n"]
end
subgraph 记忆["📌 记忆口诀"]
M["两数之和哈希表<br/>边查边存是关键<br/>先找差值后存入<br/>一次遍历搞定它"]
end
题目 --> 思路 --> 解法 --> 复杂度 --> 记忆
</div><br><br>
来源：https://www.cnblogs.com/EXQSLoveForever/p/19371119
頁:
[1]