LeetCode实战001 两数之和

原题链接

题目描述

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

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

输入示例：

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

输出：

[0, 1]

思路解读

题目不难理解，给定的输入是一个数组nums和整数target，需要找到nums[i]+nums[j]==target，并返回i, j

假设的含义是，当你找到了这样一组i，j时，可以立即返回，同时要注意返回的索引值不能相同。

解法一：暴力循环

这个解法应该是像我这样的菜鸡能想到的第一个方法。两个循环嵌套，第一个循环遍历数组，每次取出的元素假设叫x，第二个循环则是遍历数组剩余部分，查找是否存在target-x这个元素。

显然，这个解法的时间复杂度是，空间复杂度是

#include <iostream>
#include <vector>
using namespace std;

class Solution{
public:
    //暴力解法 
    vector<int> twoSum(vector<int> &nums, int target){
        vector<int> idx;
        vector<int>::iterator i = nums.begin();
        while(i != nums.end()-1)
        {
            vector<int>::iterator j = i+1;
            while(j!=nums.end())
            {
                if(*i + *j==target)
                {
                    idx.push_back(i-nums.begin());
                    idx.push_back(j-nums.begin());
                    return idx;
                }
                j++;
            }
            i++;
        }
        return idx;
    }
};

这个方法比较简单，不再用注释解释思路。虽然思路比较简单，由于题目要求用stl求解，第一次接触还是花了很久，这里说一下需要注意的点：

• 使用vector时，要引入<vector> 并且使用标准命名空间
• 遍历vector需要用迭代器，vector.begin()表示vector的首端，.end()表示尾端
• 迭代器变量i可以当成指针，用i++就可以进入下一轮循环，用*i来访问元素
• 返回索引时不能直接返回i,因为他不是int类型的对象，不能push到vector中，要用i-nums.begin()

解法二： 一遍哈希表法

在遍历数组时，可以一边将元素存入哈希表，一边从已存入的值中查找目标解。

#include <iostream>
#include <vector>
#include <map> 
using namespace std;

class Solution{
public:
    //一遍map解法 
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> map;
        for(int i=0; i<nums.size(); i++){
            int x = target - nums[i];//x是目标值
            //在这里数组的元素是map的key,数组的下标才是map的value
            //find(x)是查找是否有key==x，并返回以key开始的迭代器
            //如果想要得到value，则需访问second成员
            if(map.find(x)!=map.end())
                return {map.find(x)->second, i};
            map[nums[i]]=i; 
        }
        return{};
    }   
};

时间复杂度：，因为只遍历了数组一次，且find()函数只需的时间。

空间复杂度：，因为需要用map来存储数组元素。