前言

我是一位程序设计的初学者，对程序设计非常有兴趣，希望在这个系列的Leetcode挑战中能提升自我，以及把我所知的知识以精简的方式分享给大家，当中如有参考资料皆会附在文末，也很欢迎大家给我建议和指导！

1. Two Sum

TwoSum是Leetcode题库中的第一题，也是许多人第一次来到这个网站会先着手的一题，虽然按照题目编号刷题并不是一个很好的作法，但这一题确实是一个很好的题目，需要用到资料结构的技巧，并且展示了演算法的重要性，因此挑选这一题作为第一天的挑战。

题目

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.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

题目的意思是希望我们能在nums这个整数列表中，找到两两相加能够刚好等於target的元素所在位置(index)，并用阵列的方式回传，并且题目保证洽好只会有一组符合。

暴力解法

看到这个题目最先想到的就是用两个回圈直接把题目的要求，把每个可能的组合相加後确认有无符合target的答案，有的话就回传相对的位置，以下是C++的程序码

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 {i, j};
                }
            }
        }
        return {};
    }
};

这样的解法在Leetcode上以C++是会通过的，但是非常的慢，主要的原因就在於这样子两层回圈的暴力解法，所使用的时间复杂度是big O(n^2)，以下说明更为巧妙的解法。

HashMap解法

HahsMap是由Key和value所组成，在HashMap中Key是唯一的，且一个Key会对应到一个Value，而透过HashMap可以实现以接近big O(1)的时间复杂度来确认资料是否存在，以及其对应的值Value为何。
因此在本题中我们可以先建立一个HashMap，并透过一个for回圈，以元素为Key、其所在位置（index）为Value存进HashMap，并且每次以Target减去走访的整数，如果此结果正好为HashMap中某个Key，那我们就针对相对应的value和当下走访到的位置，存成一个阵列并回传，这样一来可以将时间复杂度降低到big O(n)。以下是程序码的实现

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target){
        unordered_map<int, int> Hash_Map; //建立HashMap
        for(int i=0;i<nums.size();i++){
            if (Hash_Map.find(target-nums[i]) != Hash_Map.end()){ // 如果找到在HashMap中存在想要找的Key
                return {i, Hash_Map[target-nums[i]]}; //那就回传现在的index与相对应的Value
            }
            Hash_Map[nums[i]] = i; //存入HashMap
        }
        return {};
    }
};

参考资料

https://leetcode.com/problems/two-sum/
https://leetcode.com/problems/two-sum/discuss/674/C%2B%2B-one-pass
https://zh.wikipedia.org/wiki/%E5%93%88%E5%B8%8C%E8%A1%A8