欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【leetcode】#1 Two Sum【Hash】【Easy】

程序员文章站 2022-07-15 14:30:52
...

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

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

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

题目大意

给出一个整数数组,你需要返回满足数组中相加等于一个目标值的两个数的索引,题目假设给出的数据必有一个解,并且你不能用同一个元素两次

解题思路

利用Hash的思想,给每个输入的值计数,对数组中的每个数判断是否有数相加等于目标值,若有则找到目标值的位置,返回这两个位置。

AC代码

#include <iostream>
#include <vector>
#include <map>
using namespace std;
map<int, int> mp;
vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> ans;
    for(int i = 0; i < nums.size(); i++) {
        mp[nums[i]]++;                                                      //记录每个值出现的次数
    }
    for (int j = 0; j < nums.size(); ++j) {
        if(mp[target - nums[j]] >= 1) {                                     //若两数相加等于target的值存在
            if(target - nums[j] == nums[j] && mp[nums[j]] == 1) continue;   //防止一个数被用两次
            int x = j + 1;
            while (nums[x] != target - nums[j]) x++;                        //寻找另一个数的位置
            ans.push_back(j);
            ans.push_back(x);
            break;
        }
    }
    return ans;
}

int main() {
    vector<int> test = {2, 7, 11, 15};
    vector<int> ans = twoSum(test, 9);
    for(int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
    return 0;
}