infrastructureDataStructure1

发表于 分类于 ，

题目描述[原题连接][https://leetcode-cn.com/problems/two-sum/]

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

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

示例:

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

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

算法描述

​ 定义一个哈希表，遍历数组nums，如果最后要得到的和减去当前遍历到的值再哈希表中存在获取两个值的下标，返回两个下标即可；

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> twoSum(vector<int>& n, int t) {
        unordered_map<int,int> mp;
        vector<int> ans;
        for(int i=0;i<n.size();i++){
            if(mp.count(t-n[i])==1){
                ans.push_back(mp[t-n[i]]);
                ans.push_back(i);
                return ans;
            }
            mp.insert(pair<int,int>(n[i],i));
        }
        return ans;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> hm  = new HashMap<Integer,Integer>();
        int[] ans = new int[2];
        for (int t = 0;t<nums.length;t++){
            if(hm.containsKey(target-nums[t])){
                ans[0] = hm.get(target-nums[t]);
                ans[1] = t;
                break;
            }
            hm.put(nums[t],t);
        }
        return ans;
    }
}