LeetCode 1.两数之和（数组、哈希表）

刺骨的言语ヽ痛彻心扉 2023-02-18 01:50 11阅读 0赞

>  写在前面：大家好！我是`ACfun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。最近萌生了刷LeetCode的想法，所以我打算从LeetCode简单的题目开始做起，攻陷LeetCode。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

原题链接：[LeetCode 1.两数之和][LeetCode 1.]

### 文章目录 ###

*  题目信息
 *   *  题目描述
     *  示例
 *  解题思路
 *   *  暴力解题
     *   *  思路
         *  时间复杂度
         *  解题代码(C++)
         *  提交情况
     *  hashmap解法
     *   *  思路
         *  时间复杂度
         *  解题代码(c++)
         *  提交情况

# 题目信息 #

## 题目描述 ##

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。  
 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

## 示例 ##

>  给定 nums = \[2, 7, 11, 15\], target = 9  
>  因为 nums\[0\] + nums\[1\] = 2 + 7 = 9  
>  所以返回 \[0, 1\]

# 解题思路 #

## 暴力解题 ##

### 思路 ###

最简单的思路就是暴力解题了，我们可以使用两层for循环遍历整数数组nums，直到遍历完整个数组。先建立一个空的vector ans，如果有连个数 i 和 j，使得 i + j = target,那么就将两个数的下标添加到ans中并返回。如果遍历完整个nums数组都找不到那么就直接返回空的ans。  
 有关vector的使用可以看一下我之前的博客：[C++STL之vector详解][C_STL_vector]

### 时间复杂度 ###

因为是使用的两层for循环，所以该方法的时间复杂度为：O(n^2)

### 解题代码(C++) ###

class Solution { 
    public:
        vector<int> twoSum(vector<int>& nums, int target) { 
            vector<int> ans;
            int size = nums.size();
            for(int i = 0;i < size-1;i++){ 
                for(int j = i + 1;j < size;j++){ 
                    if(nums.at(i) + nums.at(j) == target){ 
                        ans.push_back(i);
                        ans.push_back(j);
                        return ans;
                    }
                }
            }
            return ans;
        }
    };

### 提交情况 ###

![for][]

## hashmap解法 ##

### 思路 ###

上一个思路虽然很容易就可以想到了，但是时间复杂度为O(n^2)。比较高，时间复杂度再低一点我们可以使用C++中STL的map，map是一种有序无重复的关联容器，底层实现是一个红黑树（一种严格意义上的平衡二叉树），其查找的时间复杂度为O(log(n))。使用map可以将时间复杂度从 O(n^2)降低到了O(nlog(n))，但是我们可以进一步的降低时间复杂度。我们可以使用C++中STL的unordered\_map，unordered\_map是一种无序的map，其底层实现为哈希表，其查找的时间复杂度为O(1)。  
 所以我们可以使用unordered\_map来解这道题目，使用它我们又可以进一步的降低时间复杂度，将时间复杂度由O(nlog(n))降到了O(n)。  
 我们每次只寻找第二个数nums\[i\]，那么第一个数就为aim = target - nums\[i\]，在遍历到nums\[i\]时如果我们建立的unordered\_map中没有aim，即 target - nums\[i\] != aim，那么就将 nums\[i\] 作为键(key)，将 nums\[i\] 的下标作为值存储到unordered\_map中，继续循环遍历，直到遍历完整个nums。  
![解题思路][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]

### 时间复杂度 ###

使用unordered\_map解题的时间复杂度为：O(n)。

### 解题代码(c++) ###

class Solution { 
    public:
        vector<int> twoSum(vector<int>& nums, int target) { 
            unordered_map<int,int> hash;
            int numsSize = nums.size();
            for(int i = 0;i < numsSize;i++){ 
                int aim = target - nums[i];
                if(hash.count(aim)){ 
                    return { hash[aim],i};
                }
                hash[nums[i]] = i;
            }
            return { };
        } 
    };

### 提交情况 ###

![hash][]

--------------------

> 未完待续，持续更新中……  
> ![666][]

[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[LeetCode 1.]: https://leetcode-cn.com/problems/two-sum/
[C_STL_vector]: https://ac-fun.blog.csdn.net/article/details/105507724
[for]: https://img-blog.csdnimg.cn/2020061513151634.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200615133805434.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3,size_16,color_FFFFFF,t_70
[hash]: https://img-blog.csdnimg.cn/20200615131345345.png
[666]: https://img-blog.csdnimg.cn/20200615132236445.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3,size_16,color_FFFFFF,t_70