Leetcode数组easy | 1.两数之和
2018-11-01 本文已影响22人
Ivan_Lan
（一）两数之和
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例:
给定 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; # 返回向量容器类型
}
};
