有空就看看的leetcode1——两数之和（c++版）

拼搏现实的明天。 2023-06-25 14:28 5阅读 0赞

### 有空就看看的leetcode1——两数之和（c++版） ###

*  学习前言
 *  两数之和题目
 *  几个需要用到的函数
 *  解法
 *   *  1、遍历法
     *  2、哈希表法

# 学习前言 #

有点紧张，决定看看leetcode。  
![在这里插入图片描述][20190723170158884.jpg_pic_center]

# 两数之和题目 #

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = \[2, 7, 11, 15\], target = 9

因为 nums\[0\] + nums\[1\] = 2 + 7 = 9  
所以返回 \[0, 1\]

# 几个需要用到的函数 #

1、建立vector容器

vector<int> twoSum;

2、容器里加东西

twoSum.push_back(i)

3、建立hash表

map<int,int> hashmap;

4、hash表加东西

hashmap[target-nums[i]]=i;

# 解法 #

## 1、遍历法 ##

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

思路：  
**遍历所有容器内的组合，当满足条件时，则返回对应的两个序号。**

\-时间复杂度：O(n2)。  
\-空间复杂度：O(1)。

## 2、哈希表法 ##

class Solution {
        
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
        
            vector<int> twoint;
            map<int,int> hashmap;
            for(int i=0;i<nums.size();i++){
        
                if(hashmap.count(nums[i])!=0){
        
                    twoint.push_back(hashmap[nums[i]]);
                    twoint.push_back(i);
                }
                hashmap[target-nums[i]]=i;
            }
            return twoint;
        }
    };

思路：  
**利用hash表建立对应，将target相对于nums\[i\]的另一半保存在hashmap里当作索引，结果对应另一半的序号。  
随着i的变化，如果nums\[i\]在hash表中有对应的序号，则代表二者配对，将两个的序号保存下来。**

\-时间复杂度：O(n)。  
\-空间复杂度：O(n)。

[20190723170158884.jpg_pic_center]: https://img-blog.csdnimg.cn/20190723170158884.jpg#pic_center