Fork me on GitHub

leetcode之1.两数之和

发表于 | 分类于
字数统计 400 字 | 阅读时长 1 分钟

题目描述：

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

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

示例:

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

解题思路：

思路一：

​ 暴力搜索,时间复杂度: $O(n^2 )$,空间复杂度: ${O(1)}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<int> a;
    
    vector<int> twoSum(vector<int>& nums, int target) {
        
        for(int i = 0; i < nums.size(); i++)
    {
         for(int j = i + 1; j < nums.size(); j++)
         {

         	if(target == nums[i] + nums[j])
         	{
         		a.push_back(i);
         		a.push_back(j);
                break;
         	}
         }
    }
   
   return a;
        
        
    }
};

思路二：

​ 运用map，vector，时间复杂度: ${O(n)}$,空间复杂度: $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> twoSum(vector<int>& nums, int target) {
        // 使用unordered_map来存储数据，第一个是数，第二个是下标
        // 貌似使用map也可以
        map<int,int> mtemp;
        vector<int> vec;
        // 第一遍将所有的数据插入到map里面,注意，没有重复的数字，所以键值唯一
        for(int i = 0;i < nums.size();++i)
        {
            mtemp[nums[i]] = i;
        }
        // 第二遍扫描查找
        for (int i=0; i<nums.size(); ++i){
            // 从map中查找是否存在元素
            int nextval = target - nums[i];
            // 如果存在并且下标不为i
            if( mtemp.count(nextval) && mtemp[nextval] != i){
                // 保存并且推出
                vec.push_back(i);
                vec.push_back(mtemp[nextval]);
                break;
            }
        }
        return vec;
    }