Leetcode数组easy | 1.两数之和

（一）两数之和

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

---

Python版

解法一：两轮遍历。时间复杂度: O(N^2) 空间复杂度: O(1)

class Solution(object):
    def twoSum(self, nums, target):
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

解法二：时间复杂度: O(N) 空间复杂度: O(N)

• 建立字典 lookup 存放第一个数字，并存放该数字的 index
• 判断 lookup 种是否存在： target - 当前数字， 则表面 当前值和 lookup中的值加和为 target.
• 如果存在，则返回： target - 当前数字 的 index 和 当前值的 index

class Solution(object):
    def twoSum(self, nums, target):
        lookup = {}
        for i, num in enumerate(nums):   
            if target - num in lookup:
                return [lookup[target-num], i]
            else:
                lookup[num] = i

enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中

• seasons = ['Spring', 'Summer', 'Fall', 'Winter']
• list(enumerate(seasons))
• [(0, 'Spring'), (1, 'Summer'), (2, 'Fall'), (3, 'Winter')]

C++版

方案一：时间复杂度: O(NlgN) 空间复杂度: O(N)

采用双指针法，先将数组排序形成了一个有序的区间，指针i，j分别指向头尾

• 当 nums1[i] + nums[j] > traget 时，j--，
• nums[i] + nums[j] < target 时，i++，
• 直到 nums[i] + nums[j] == target

class Solution 
{
public:    # 关键字 public 确定了类成员的访问属性
    vector<int> twoSum(vector<int>& nums, int target)   # 返回值类型为vector<int>   函数参数有vector<int>类型和int
    {
        vector<pair<int,int> > nums1;   # 定义一个新容器
        for(int i = 0;i < nums.size();++i)   # size 当前使用数据的大小
            nums1.push_back(make_pair(nums[i],i));   # 将值和索引对添加进容器
        sort(nums1.begin(),nums1.end());  # sort  从小到大排序
        int i = 0,j = nums1.size() - 1;   # 头指针i 和尾指针 j 
        vector<int> ret;  # 定义新容器
        while(i < j)   # 根据指针条件循环
        {
            if(nums1[i].first + nums1[j].first == target)   # 判断指针对应容器nums1中的两个值的和
            {
                ret.push_back(nums1[i].second);   # 将符合条件的索引添加进容器ret
                ret.push_back(nums1[j].second);
                return ret;   # 返回容器
            }
            nums1[i].first +nums1[j].first < target ? ++i : --j;   # 问号运算 (表达式1)？(表达式2):(表达式3)  如果表达式1成立则执行表达式2，否则执行表达式3
        }
    }
};

方案二：时间复杂度: O(N) 空间复杂度: O(N)

c++中提供unordered_map 的容器，unordered_map 中的元素没有按照它们的键值或映射值的任何顺序排序， 而是根据它们的散列值组织成桶,以允许通过键值快速访问单个元素（具有常数平均时间复杂度） ,将先出现的元素储存在 unorder_map 中，遍历数组，每次查找 target - nums[i] 是否存在即可。

class Solution 
{
public:
   vector<int> twoSum(vector<int>& nums, int target)
   {
       unordered_map<int, int> m;  # 定义新容器m，类似于python的字典的键值对
       vector<int> res;   # 定义新容器res
       for (int i = 0; i < nums.size(); ++i) {
           m[nums[i]] = i;   # 将传入的nums元素添加进m，值作为键，索引作为值
       }

       for (int i = 0; i < nums.size(); ++i) {   # 遍历数组
           int t = target - nums[i];    
           if (m.count(t) && m[t] != i) {      # count() 如果m中存在为t的键，返回1。存在值t，且t的索引不为i
               res.push_back(i);     # 第一个索引添加进res
               res.push_back(m[t]);  # 满足条件的第二个索引添加进res
               break;
           }
       }
       return res;  # 返回向量容器类型
   }
};

参考：
awesome-algorithm
awesome-algorithm