leetcode#1
2019-05-15 / Luo Jinrong   

题目描述

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

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

示例:

1
2
3
4
给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
  • 方法一
  • 暴力求解，$O(n^2)$遍历数组，找到一个数nums[i],再找nums[j],判断nums[i]+nums[j]是否等于target
  • 代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        int s=nums.size();
        for(int i=0;i<s-1;i++){
            for(int j=i+1;j<s;j++){
                if(nums[i]+nums[j]==target){
                    ans.push_back(i);
                    ans.push_back(j);
                    return ans;
                }
            }
        }
        return ans;
    }
};
  • 方法二
  • 用哈希表存储数组里的值，然后遍历哈希表，当前值为i,再找哈希表中是否存在target-i
  • 发现虽然题目说不能重复利用同样的元素，但其实他的意思是不能用同一位置的元素，不同位置的相同值可以重复使用，所以在存入哈希表的时候做一个特判
  • 算法复杂度$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
25
26
27
28
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans,ans1;
        map<int,int> m;
        int count=0;
        for(int i=0;i<nums.size();i++){//把nums里面的数存到map里 map里的只为<nums里的值，nums下标>
            if(nums[i]==target/2&&!(target&1)){//当target为偶数 考虑两数相等的情况
                ans1.push_back(i);
                count++;
                if(count==2){
                    return ans1;
                }
            }
            m[nums[i]]=i;
        }
        pair<map<int,int>::iterator,map<int,int>::iterator> pr;
        for(map<int,int>::iterator i=m.begin();i!=m.end();i++){//遍历map
            pr=m.equal_range(target-i->first);//找到对应相加为target 的值
            if(pr.first!=pr.second){//存在，则把两个下标存到答案中
                ans.push_back(i->second);
                ans.push_back(pr.first->second);
                break;
            }
        }
        return ans;
    }
};

return 0;

本文链接：
https://luojinrong.github.io/2019/05/15/leetcode-1/