leetcode1. Two Sum_i'm new to coding and now i want to get the sum of-CSDN博客

本文链接：https://blog.csdn.net/ProgrammeringLearner/article/details/64124609

本文探讨了两数之和问题的两种算法实现：暴力求解法与哈希表法。介绍了如何使用unordered_map降低时间复杂度，并针对数组中存在重复元素的情况提出解决方案。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

Easy程度题:

题目:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

最容易想到的是暴力求解，复杂度O(n*n)，效率较低

代码如下

class Solution
{
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        int i=0,j=0;
        int len = nums.size();
        vector<int> result;
        for(i; i < len; i++)
            for(j = i + 1; j < len; j++)
                if(nums[i] + nums[j] == target)
                {
                     result.push_back(i);
                     result.push_back(j);
                     break;
                }
          
        return result;
    }
};

之后了解过了unordered_map结构，可以用这个来做，复杂度为O（n）

代码

class Solution
{
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        unordered_map<int,int> map;
        int n = nums.size();
        vector<int> result;
        for (int i = 0; i < n; i++)
            map[nums[i]] = i;
        
        for (int i =0; i < n; i++)
        {
            int temp = target - nums[i];
            if (map.find(temp) != map.end() && map[temp] > i)
            {
                result.push_back(map[nums[i]]);
                result.push_back(map[temp]);
                break;
            }
        }
        
        return result;
    }
};

这样做有一个问题就是数组中有重复元素时会覆盖，unordered_map为Key-Value结构，当有相同的Key值时，Value值会进行覆盖，这样当数组为[3,3] target = 6 时就会遇到问题

为了解决这个问题，我们可以一边将数组元素向前推进，一边将键值对Key-Value存储到unordered_map中，每到第i个元素就另temp = target - nums[i] 在之前存储的Key值中查找temp

AC解

class Solution
{
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        unordered_map<int,int> map;
        int n = nums.size();
        vector<int> result;
       
        for (int i =0; i < n; i++)
        {
            int temp = target - nums[i];
            if (map.find(temp) != map.end())
            {
                result.push_back(map[temp]);
                result.push_back(i);
                break;
            }
            
            map[nums[i]] = i;
        }
        
        return result;
    }
};