两数之和，时间复杂度为O(n)

1. 题目描述

2. 实现

#include <iostream>
#include <vector>
#include <unordered_map>using namespace std;class Solution
{
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> numMap;for (int i = 0; i < nums.size(); i++) {int complement = target - nums[i];if (numMap.find(complement) != numMap.end()){return { numMap[complement],i };}numMap[nums[i]] = i;}}private:
};int main() {// 示例1std::vector<int> nums1 = { 2, 7, 11, 15 };int target1 = 9;Solution solution;std::vector<int> result1 = solution.twoSum(nums1, target1);if (!result1.empty()) {std::cout << "[" << result1[0] << ", " << result1[1] << "]" << std::endl;}else {std::cout << "No solution found." << std::endl;}// 示例2std::vector<int> nums2 = { 3, 2, 4 };int target2 = 6;std::vector<int> result2 = solution.twoSum(nums2, target2);if (!result2.empty()) {std::cout << "[" << result2[0] << ", " << result2[1] << "]" << std::endl;}else {std::cout << "No solution found." << std::endl;}// 示例3std::vector<int> nums3 = { 3, 3 };int target3 = 6;std::vector<int> result3 = solution.twoSum(nums3, target3);if (!result3.empty()) {std::cout << "[" << result3[0] << ", " << result3[1] << "]" << std::endl;}else {std::cout << "No solution found." << std::endl;}return 0;
}

3. 时间复杂度分析

1. 算法描述
   给定的算法使用了一个unordered_map（哈希表）来解决两数之和的问题。算法在一次遍历数组nums的过程中，对于每个元素nums[i]，计算其与目标值target的差值complement = target - nums[i]，然后检查complement是否存在于哈希表中。如果存在，则找到了两个数的和等于target，返回它们的下标；如果不存在，则将当前元素nums[i]及其下标i存入哈希表中，继续遍历下一个元素。
2. 时间复杂度分析

• 最好情况：
  如果数组中的前两个元素之和就等于目标值target，那么算法只需要进行两次操作（一次计算差值，一次在哈希表中查找）就能找到答案。此时时间复杂度为。

• 最坏情况：
  假设哈希表没有发生冲突，对于数组中的每个元素，哈希表的插入和查找操作的时间复杂度都为O(1)。

  算法需要遍历整个数组nums一次，数组长度为，每次遍历都进行常数时间的操作（计算差值、哈希表查找和插入）。

  所以，在最坏情况下，时间复杂度为，其中是数组nums的长度。

• 平均情况：
  平均而言，对于长度为的数组，算法仍然只需要遍历数组一次，每次遍历中的操作时间复杂度都是常数级别的。

  因此，平均时间复杂度也是O(n)。

综上所述，该算法的时间复杂度为O(n)，其中是输入数组nums的长度。这种算法相较于暴力解法（两层嵌套循环，时间复杂度为O($n^2$)）在效率上有很大的提升。