0001._Two_Sum.md

1. Two Sum

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/two-sum
• https://leetcode-cn.com/problems/two-sum

内容描述

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

解题方案

思路 1 - 时间复杂度: 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:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        vector<pair<int,int> > nums1;
        for(int i = 0;i < nums.size();++i)
            nums1.push_back(make_pair(nums[i],i));
        sort(nums1.begin(),nums1.end());
        int i = 0,j = nums1.size() - 1;
        vector<int> ret;
        while(i < j)
        {
            if(nums1[i].first + nums1[j].first == target)
            {
                ret.push_back(nums1[i].second);
                ret.push_back(nums1[j].second);
                return ret;
            }
            nums1[i].first +nums1[j].first < target ? ++i : --j;
        }
    }
};

思路 2 - 时间复杂度: 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;
       vector<int> res;
       for (int i = 0; i < nums.size(); ++i) {
           m[nums[i]] = i;
       }
       for (int i = 0; i < nums.size(); ++i) {
           int t = target - nums[i];
           if (m.count(t) && m[t] != i) {
               res.push_back(i);
               res.push_back(m[t]);
               break;
           }
       }
       return res;
   }
};