0001. Two Sum ============= 题目信息 -------- :题号: 0001. 两数之和 :难度: Easy :主题: 数组、哈希表、排序、双指针 :原题: `LeetCode 0001 `_ :重点: 从枚举下标对推导到补数查询,再利用有序性或哈希索引消除重复搜索 题目重述 -------- 给定整数数组 ``nums`` 和整数 ``target``,需要找到两个不同的零基下标 ``i`` 和 ``j``,使 ``nums[i] + nums[j] == target``,并返回这两个下标。 同一个位置不能重复使用。数组不保证有序,返回的两个下标也不要求按升序排列。题目保证恰好存在一个有效答案。 约束条件: * ``2 <= nums.length <= 10^4``; * ``-10^9 <= nums[i] <= 10^9``; * ``-10^9 <= target <= 10^9``。 自建示例 -------- * 普通命中:``nums = [4, 1, 9, 5]``、``target = 10``,数值 ``1`` 和 ``9`` 位于下标 ``1``、``2``,返回 ``[1, 2]``; * 相同数值:``nums = [4, 1, 4, 10]``、``target = 8``,两个 ``4`` 来自不同位置,返回 ``[0, 2]``; * 负数参与:``nums = [-3, 7, 2, 11]``、``target = 4``,返回 ``[0, 1]``; * 最小规模:``nums = [-5, 100]``、``target = 95``,数组只有两个元素,返回 ``[0, 1]``。 C++ 实现 -------- .. code-block:: cpp #include #include #include #include class Solution { private: std::vector bruteForce(const std::vector& nums, int target) { for (int left = 0; left < static_cast(nums.size()); ++left) { for (int right = left + 1; right < static_cast(nums.size()); ++right) { const long long sum = static_cast(nums[left]) + nums[right]; if (sum == target) { return {left, right}; } } } return {}; } std::vector sortAndTwoPointers(const std::vector& nums, int target) { std::vector> items; items.reserve(nums.size()); for (int index = 0; index < static_cast(nums.size()); ++index) { items.emplace_back(nums[index], index); } std::sort(items.begin(), items.end()); int left = 0; int right = static_cast(items.size()) - 1; while (left < right) { const long long sum = static_cast(items[left].first) + items[right].first; if (sum == target) { return {items[left].second, items[right].second}; } if (sum < target) { ++left; } else { --right; } } return {}; } std::vector twoPassHash(const std::vector& nums, int target) { std::unordered_map indexByValue; indexByValue.reserve(nums.size()); for (int index = 0; index < static_cast(nums.size()); ++index) { indexByValue[nums[index]] = index; } for (int index = 0; index < static_cast(nums.size()); ++index) { const int need = target - nums[index]; const auto found = indexByValue.find(need); if (found != indexByValue.end() && found->second != index) { return {index, found->second}; } } return {}; } std::vector onePassHash(const std::vector& nums, int target) { std::unordered_map seen; seen.reserve(nums.size()); for (int index = 0; index < static_cast(nums.size()); ++index) { const int need = target - nums[index]; const auto found = seen.find(need); if (found != seen.end()) { return {found->second, index}; } seen[nums[index]] = index; } return {}; } public: std::vector twoSum(std::vector& nums, int target) { return onePassHash(nums, target); } }; 题解 ---- 原始搜索空间 ~~~~~~~~~~~~ 最直接的方法是枚举所有 ``i < j`` 的下标对。长度为 ``n`` 的数组共有 ``n(n - 1) / 2`` 个不同下标对,``bruteForce`` 恰好把这些候选全部检查一次,因此不会遗漏答案。 一次候选检查只做一次加法和比较,真正的瓶颈是候选数量达到二次规模。固定一个位置后,内层循环仍要逐个访问其后的元素,反复寻找能够与当前值组成 ``target`` 的数。 重复工作不是计算两数之和,而是“在其余元素中寻找一个指定数值”。 补数转换 ~~~~~~~~ 条件 ``nums[i] + nums[j] == target`` 可以改写为 ``nums[i] == target - nums[j]``。当当前位置 ``j`` 已经确定时,另一个位置需要具有的数值也随之确定,这个数值就是补数 ``target - nums[j]``。 问题由“同时枚举两个未知位置”转变为:选择一个当前位置,再查询它的补数是否存在以及补数位于哪个下标。 这个转换产生两条优化路线:排序让候选具有单调性,可以批量排除不可能的下标;哈希表则直接建立从数值到下标的索引,使补数查询不再线性扫描。 排序双指针 ~~~~~~~~~~ 原数组无序时,当前和过大或过小都不能确定应排除哪个元素。``sortAndTwoPointers`` 先建立 ``(数值, 原始下标)`` 副本并按数值排序,使剩余区间具有单调性,同时避免修改输入并保留最终需要返回的原始下标。 令 ``left`` 指向剩余区间最小值,``right`` 指向最大值: * 当前和小于 ``target`` 时,最小值与区间最大值配对仍然过小,它与区间内任何更小的数配对只会更小,因此可以排除当前 ``left``; * 当前和大于 ``target`` 时,最大值与区间最小值配对仍然过大,它与区间内任何更大的数配对只会更大,因此可以排除当前 ``right``; * 当前和等于 ``target`` 时,两个元素保存的原始下标就是答案。 暴力法每次只检查并排除一个下标对,双指针每次移动都排除以当前端点为一端的一整组候选。代价是构造副本并排序,总时间由排序主导。 完整哈希索引 ~~~~~~~~~~~~ 另一条路线是直接解决补数查询。``twoPassHash`` 第一遍扫描建立 ``数值 -> 下标`` 的完整索引,第二遍对每个位置查询补数。 查询命中后还必须检查 ``found->second != index``。例如只有一个数值 ``4`` 时,查询补数 ``4`` 可能得到当前位置本身,而题目禁止同一个位置使用两次。若数组中存在两个相同的答案值,映射保存其中一个下标,扫描另一个位置时就能通过不同下标检查。 完整索引把每次补数搜索从线性扫描降为期望常数时间,使总时间降到期望 ``O(n)``。不过它把“建立索引”和“寻找答案”分成两次遍历,即使答案很早出现,也要先保存整个数组。 历史前缀索引 ~~~~~~~~~~~~ 扫描到 ``index`` 时,答案的另一个位置只需从已经处理过的前缀 ``[0, index)`` 中寻找。于是可以把建立索引和查询答案合并到同一轮扫描中。 ``onePassHash`` 在处理当前元素时先查询 ``need = target - nums[index]``。此时 ``seen`` 只包含更早的位置,查询命中后得到的下标天然与 ``index`` 不同,不再需要显式比较下标。查询失败后再写入当前值,使它从下一轮开始成为历史前缀的一部分。 查询与写入的顺序不能交换。若先写入当前值,补数与当前值相同时,当前位置可能立即匹配自己。先查询、后写入把“两个下标必须不同”直接编码进了状态范围。 状态演化 ~~~~~~~~ 以 ``nums = [4, 1, 4, 10]``、``target = 8`` 为例: .. list-table:: :header-rows: 1 * - ``index`` - ``value`` - ``need`` - 查询前的 ``seen`` - 动作 * - 0 - 4 - 4 - ``{}`` - 未命中,写入 ``4 -> 0`` * - 1 - 1 - 7 - ``{4: 0}`` - 未命中,写入 ``1 -> 1`` * - 2 - 4 - 4 - ``{4: 0, 1: 1}`` - 命中 ``4 -> 0``,返回 ``[0, 2]`` 第一个 ``4`` 到达时,历史前缀为空,所以它不能与自己配对。第二个 ``4`` 到达时,第一个 ``4`` 已经进入历史前缀,两个不同位置才形成答案。 代码演进 ~~~~~~~~ ``bruteForce`` 使用两层循环枚举两个未知位置。补数转换确定了第二个位置必须具有的数值,后续优化都围绕“如何更快找到补数”展开。 ``sortAndTwoPointers`` 通过排序建立单调性,把内层逐个尝试改成左右端点移动;它删除了内层线性枚举,但增加了带原始下标的副本和排序过程。 ``twoPassHash`` 不再依赖元素顺序,而是建立完整的数值索引。排序副本和双指针消失,补数可以直接查询;代码需要两次遍历,并显式排除当前位置与自己匹配。 ``onePassHash`` 进一步把完整索引缩减为历史前缀索引。第二次遍历和不同下标判断同时消失,代码只保留一次顺序扫描、一次补数查询和一次历史状态写入。 四种实现对应四层认识: * 不利用结构时,枚举全部下标对; * 利用有序性时,一次排除整组候选; * 建立完整索引时,直接查询补数; * 只索引历史前缀时,在一次遍历中完成查询与建表。 公开入口采用 ``onePassHash``,因为它不修改输入、不需要排序,并能在期望线性时间内返回原始下标。 复杂度分析 ~~~~~~~~~~ .. list-table:: :header-rows: 1 * - 方法 - 时间复杂度 - 工作空间 - 主要代价 * - 暴力枚举 - ``O(n²)`` - ``O(1)`` - 检查全部不同下标对 * - 排序双指针 - ``O(n log n)`` - ``O(n)`` - 构造并排序带原始下标的副本 * - 两次遍历哈希表 - 期望 ``O(n)`` - ``O(n)`` - 先建立完整索引,再查询补数 * - 一次遍历哈希表 - 期望 ``O(n)`` - ``O(n)`` - 边扫描边维护历史前缀索引 哈希表查询和写入的平均时间为 ``O(1)``,因此两种哈希方案的期望总时间都是 ``O(n)``。极端哈希冲突下的最坏时间取决于容器实现,不能把它们写成严格线性。