tags:
  - DSA

L3. Two Sum

Description

Given an array of integers num and an integer target, return indices of two numbers such that they add up to target.

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

Brute Force Solution

暴力求解的方法，我们需要两个 for 循环遍历所有可能的数字对，因而其时间复杂度为。思路是这样的：

#include <iostream>
#include <vector>

class mySolution{
public:
    std::vector<int> twoSum(const std::vector<int>& nums, const int& target){
        for( size_t i = 0; i < nums.size(); i++){
            for( size_t j = i + 1; j < nums.size(); j++){
                if(nums[i] + nums[j] == target){
                    return{static_cast<int>(i), static_cast<int>(j)};
                }
            }
        }
        return {};
    }
};

int main(){
    std::vector<int> nums = {1,2,4,8,16,32,64,128,256};
    int target = 96;
    mySolution solution;
    std::vector<int> res = solution.twoSum(nums, target);
    if(res.size()){
        for(auto elem : res){
            std::cout << elem << std::endl;
        }
    }
    else{
        std::cout << "Negative" << std::endl;
    }
    return 0;
}

Hash Map Solution

再好一点的方法就是使用哈希表，简单的思路如下：

#include <iostream>
#include <vector>
#include <unordered_map>

std::vector<int> twoSum(const std::vector<int>& nums, int target) {
    std::unordered_map<int, int> numMap;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if(numMap.find(complement) != numMap.end()){
            return {numMap[complement], i};
        }
        numMap.insert(std::make_pair(nums[i], i));
    }
    return {};
}

int main() {
    std::vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    std::vector<int> result = twoSum(nums, target);
    for (int index : result) {
        std::cout << index << " ";
    }
    return 0;
}