###### tags: `Leetcode` `easy` `hash` `python` `c++` `Top 100 Liked Questions`

# 1. Two Sum

## [題目來源:] https://leetcode.com/problems/two-sum/

## 題目:
Given an array of integers nums and an integer target, return indices of the 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.

You can return the answer in any order.

## 解題想法:
使用hash table : key存數字，val存數字於nums中的位置

## Python(一刷):
字典.__contains__(key) : key是否出現於字典中

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        numMap = {}
        for i in range(len(nums)):
            print(numMap,i)
            if numMap.__contains__(target-nums[i]):
                return [numMap.get(target-nums[i]), i]
            else:
                numMap[nums[i]] = i

if __name__ == '__main__':
    Result = Solution()
    nums = [7,8,3,4,5]
    target = 9
    print(Result.twoSum(nums,target))

## Python(二刷):

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        map={}
        for pos,val in enumerate(nums):
            if target-val in map:
                return [pos,map[target-val]]
            else:
                map[val]=pos

## C++(一刷):
雙迴圈暴力法

#include <iostream>
#include <vector>
using namespace std;

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

int main()
{
    vector<int> nums = {2, 7, 11, 15};
    int target = 9; // [0,1]
    // vector<int> nums = {3,2,4}; int target = 6; // [1,2]
    // vector<int> nums = {3,3}; int target = 6; // [0,1]
    Solution s;
    vector<int> ret = s.twoSum(nums, target);
    cout << "[" << ret[0] << "," << ret[1] << "]\n";

    return 0;
}

//輸出 : 終端機編譯  格式: g++ <檔名> -o <想要輸出的名稱>.exe
// g++ P1.cpp -o res.exe

## C++(二刷):
使用<unordered_map>

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution
{
public:
    vector<int> twoSum(vector<int> &nums, int target)
    {
        unordered_map<int, int> dic;
        vector<int> ans;
        for (int i = 0; i < nums.size(); i++)
        {
            if (dic.find(target - nums[i]) != dic.end())
            { //找到了
                ans.push_back(dic[target - nums[i]]);
                ans.push_back(i);
                return ans;
            }
            else
            {
                dic[nums[i]] = i;
            }
        }
        return ans;
    }
};

int main()
{

    vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    Solution res;
    vector<int> ans = res.twoSum(nums, target);
    cout << "[" << ans[0] << "," << ans[1] << "]" << endl;
    return 0;
}