C++ 2Sum

2Sum 是一个传统的算法问题，在 计算机科学 和编程界广为人知。这个问题对 数据结构、算法设计 和 计算复杂性 的学生来说是基础性的。但尽管如此，这个问题似乎包含了一些重要的概念和技术，可以应用于软件开发的许多其他领域，因此，这个问题需要更深入的理解。

2Sum 问题的本质可以概括如下：你的任务是确定一个数组中是否存在两个元素，当它们相加时等于目标和。你会被提供一个整数数组和一个目标和。如果存在这样的两个元素，你需要给出它们的索引；如果不存在，则需要以明确表明没有这样的对的方式来处理。这不仅仅是一个学术问题；它在欺诈检测、金融分析甚至游戏设计等实际领域都有应用，在这些领域，理解元素或值至关重要。

仅仅解决 2Sum 问题是不够的，理解如何高效地扩展和处理这个算法问题同样重要。能够推导出既高效又适合操作的算法，这在理论和实际问题解决以及竞争性编程中都非常重要。通过结合简单的暴力解法与更好、更复杂的方法和算法，2Sum 问题是进行这些改进的完美选择。

如你所见，有几种方法可以解决 2Sum 问题，这些方法在时间、内存和复杂性方面有所不同，详细了解它们对于完全理解问题的范围非常重要。朴素方法直接且采用简单的处理方式，通常是首先考虑的方法。该过程检查数组中每个潜在的整数对之和是否等于目标和。暴力法易于实现和理解，但在大型数据集上存在一些缺点。其时间复杂度为 O(n^2)，其中 n 是数组中的元素数量，这意味着它不适合在这些特定的使用场景中使用。

随着我们对问题的深入，会采用更复杂的技术来提高解决方案的效率，例如使用哈希映射（在 C++ 中称为 unordered_map）。通过采用各种技术，例如哈希表（与暴力法的 O(n^2) 时间复杂度相比，可将时间复杂度提高到 O(n)），总有可能实现线性时间复杂度 O(n)。

因此，给定的 2Sum 问题不仅仅是找到任何一个解决方案，而是要在考虑上述限制和标准的情况下，找到所有解决方案中最优的解决方案。这引发了一些问题，例如输入验证、边界情况以及关于包含重复值和负值的整数数组的特殊情况。为了保持现实性，尽可能地将这些细微之处纳入算法中，这一点在学术界和商业界都备受重视。

2Sum 问题本身很重要，但它也引出了更复杂的情况，例如 kSum 问题，这是 3Sum 问题的扩展，目标是找到 k 个相加等于目标值的数字；或者 3Sum 问题旨在识别数组中的三个数字以达到目标值的平均值。它们引入了额外的难度，需要使用更高级的方法，如排序算法、高阶指针或递归。解决 2Sum 问题使你能够解决这些问题，因为它指导你如何处理它们。

解决 2Sum 问题时学到的原理元素在现实生活中可能非常重要。例如，在金融系统中，识别总和等于给定数量的交易可能对于检查欺诈或确保正确记录至关重要。同样，在库存管理中，满足客户需求和管理库存水平需要了解不同种类的商品如何相加以提供某些价值。在游戏开发环境中，用户体验、游戏循环设计或一套游戏设计机制可能很大程度上取决于开发人员能否在极短的时间内识别出满足某些给定要求的项目或功能的对。

问题陈述

2Sum 问题是计算机科学课程、学习资源、技术面试和编程竞赛中必不可少且刻意包含的领域之一。它在帮助实践者掌握数据结构、算法设计和计算的一些基本原理方面非常有帮助。在考虑可能的解决方案和优化之前，充分理解问题陈述非常重要。

形式化定义

假设有一个名为 nums 的 数组，其中包含若干整数，还有一个名为 target 的整数；目标是找到 nums 中两个不同数字的两个精确点，这两个数字相加等于 target。具体来说，你需要返回这两个数字的索引，使得：具体来说，你需要返回这两个数字的索引，使得

其中 index1 和 index2 是这两个数字在数组中的索引。必须理解的是，对于每个输入，都存在一个唯一的解，并且同一个元素不能使用两次来构成和。

详细分解

输入数组 (nums)

类型：输入是一个整数数组（或 C++ 中的 vector）。这些整数可以是正数、负数或零。

特征：数组中的数字可能会重复，并且给定的数字不一定按升序排列。数组可能很小，只有两三个元素，也可能包含数百万个元素，这会影响解决方案的效率。

索引：大多数编程语言，例如 C++，数组的索引从 0 开始。因此，第一个元素是索引 0，第二个是索引 1，以此类推。

目标和 (target)

类型：一个整数值，即由数组中的两个不同元素可以达到的期望和值。

范围：目标值可以是任何整数，可以是正整数、负整数或零。另一个需要考虑的是，解决方案必须能够处理各种可实现的和。

两个数字的索引：输出应该是数组中两个数字的索引，这两个数字相加等于目标值。索引可以按任何顺序返回；例如，如果找到的对的索引是 2 和 5，则函数可以返回 [2,5] 或 [5, 2] 或其他排列。

唯一性：问题保证存在一个唯一的这样的对。因此，解决方案不需要处理包含多个有效对甚至不包含任何有效对的情况，尽管良好的程序实现会包含对这种情况的考虑。

使用元素的限制：允许使用的元素是输入数组中可用的元素，并且每个元素只能使用一次。这意味着，如果目标值是数组中某个值的两倍，则数组中必须至少有两个该值，才能构成有效的对。

约束

• 时间复杂度：尽管问题陈述没有限制时间复杂度，但最优解决方案的目标是获得 O(n) 的时间复杂度，其中 n 是数组中的元素数量。理解和实现这种效率是解决此问题的学习成果之一。
• 空间复杂度：同样，最优解决方案的目标是最小化解决方案使用的额外空间。某些解决方案可能会有额外的空间复杂度，例如用于加速暴力搜索的哈希映射。

假设

是的，只有一个唯一的解。这使得问题更容易处理，因为一旦找到一个有效的匹配，你就可以停止了。

同一个元素不能使用两次。这意味着，除非数组中存在某个数字的重复项，否则如果同一个数字只出现一次，它就不能与自身配对以生成目标和。

示例说明问题

示例 1

输入： nums = [2, 7, 11, 15], target = 9

输出 [0, 1]

因为 nums[0] + nums[1] = 2 + 7 = 9。

解释：这里，数组 nums 包含四个元素。目标是找到两个相加等于 9 的不同数字。通过检查对：

2 + 7 = 9 → 索引 [0, 1]

2 + 11 = 13 ≠ 9

2 + 15 = 17 ≠ 9

7 + 11 = 18 ≠ 9

7 + 15 = 22 ≠ 9

11 + 15 = 26 ≠ 9

唯一一对相加等于 9 的是 2 和 7，它们位于索引 0 和 1。

示例 2

输入： nums = [3, 2, 4], target = 6

输出 [1, 2]

解释：因为 nums[1] + nums[2] = 2 + 4 = 6。

解释：在这种情况下，数组 nums 包含三个元素。目标和是 6。可能的对是：

3 + 2 = 5 ≠ 6

3 + 4 = 7 ≠ 6

2 + 4 = 6 → 索引 [1, 2]

2 和 4 这对数字相加等于 6，它们位于索引 1 和 2。

示例 3

输入： nums = [3, 3], target = 6

输出 [0, 1]

因为 nums[0] + nums[1] = 3 + 3 = 6。

解释：这个例子突出了对重复元素的处理。数组 nums 包含两个相同的元素，都是 3。目标和是 6，因为 3 + 3 = 6，所以有效对的索引是 [0, 1]。

边缘情况

为了确保健壮性，在解释问题陈述时考虑各种边界情况至关重要。为了确保健壮性，在解释问题陈述时考虑各种边界情况至关重要。

• 小型数组：元素少于两个的数组无法构成有效对。同样，这个问题假定存在一个确切的解，但在实际中可能需要输入验证。
• 所有元素都相同：如果数组中的所有元素都相等，并且目标值是该元素值的两倍，那么任何两个不同的索引都可以构成一对。例如：

输入： nums = [5, 5, 5, 5], target = 10

输出：任何一对不同的索引，例如 [0, 1]

负数：数组可能包含负数，目标和可能涉及正数和负数的组合。例如：

输入： nums = [-3, 4, 3, 90], target = 0

输出 [0, 2]

解释：因为 nums[0] + nums[2] = -3 + 3 = 0。

数组中的零：如果目标和为零，解决方案可能涉及零的对或可以相互抵消的数字。

输入： nums = [0, 4, 3, 0], target = 0

输出 [0, 3]

解释：因为 nums[0] + nums[3] = 0 + 0 = 0。

对算法设计的影响

尽可能充分地理解问题陈述，以便设计出优秀的算法，这总是至关重要的。以下方面受到问题规范的影响：

• 唯一解保证：这一点尤其有价值，因为对于这类问题，我们可以证明只有一个解。例如，算法可以在找到第一个有效元素对后立即停止，从而节省计算时间。
• 元素唯一性：由于同一个元素不能使用两次，因此索引必须是唯一的，算法会实现这一点。这会影响元素在数组、哈希映射或其他数据结构中的存储和验证方式。
• 性能考虑：问题陈述巧妙地暗示了对时间和空间效率高的算法的需求，尤其是因为数组可能很大。这要求正确选择适用的数据结构类型和适当的优化技术。

输出

 
Indices: 0, 1   

时间复杂度分析

该方法的 time complexity 为 O(n^2)，其中 n 是数组中的元素数量。这是因为对于每个元素，我们都要遍历剩余的元素，导致二次方的时间复杂度。此方法易于实现，但对于大型输入规模来说效率不高。

优化方法：使用哈希映射

输出

 
Indices: 0, 1   

说明

数字 2 和 7 在向量中位于索引 0 和 1，它们的和等于目标值 9。因此，输出是：索引：0, 1。

时间复杂度分析

该方法的 time complexity 为 O(n)，其中 n 是数组中的元素数量。这是因为我们只遍历数组一次，并且哈希映射中的每次查找和插入操作平均为 O(1)。空间复杂度也为 O(n)，因为哈希映射需要额外的存储空间。