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
```cpp
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] 是否存在即可。
cpp 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; } };
