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

1 Tow Sum

程序员文章站 2024-02-29 10:46:46
...

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.


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

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


解题代码如下:

#include<stdio.h>
#include <iostream>
#include <vector>
#include<algorithm>
#include<functional>
#include<tr1/unordered_map>
using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers,int target){
        std::tr1::unordered_map<int,int> hash;
        vector<int> result;
        for(int i=0;i<numbers.size();i++){
            int numberToFind = target-numbers[i];//用目标值依次减去向量中的元素得到剩余值
            if(hash.find(numberToFind)!=hash.end()){//判断剩余值是否在hash表中出现,如果出现则获取其对应的键值
                result.push_back(hash[numberToFind]);
                result.push_back(i);
                return result;
            }
            hash[numbers[i]]=i;//不在表中则加入表中

        }
        return result;
    }
};

int main()
{
    Solution s;
    vector<int> vec_A;
    int target,c,n;
    cin>>target;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>c;
        vec_A.push_back(c);
    }
    vector<int> result = s.twoSum(vec_A,target);
    cout<<result[0]<<result[1]<<endl;
    return 0;
}

整个思路很简单啊,将vector转换成一个值和下表对应的hash表,然后用目标值依次减去vector中的值得到剩余值,判断剩余值是否在hash表中,有则返回。


相关标签: leetcode 算法