two sum python_LeetCode 1 Two Sum 两数之和1（Python，C++）

最近准备开始重新来刷个题了，之前leetCode 前400道刷了两三遍了吧

但是感觉以前好多题刷是刷了

归纳整理的不太行啊

然后刷完了解法就都忘了

那也没什么用啊

所以准备一遍刷一边归纳整理一下

Two Sum：题目描述：给定一个整数数组 nums和一个目标值target，该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

题目已经告诉了每种输入的nums里面只有一个答案，而且同一个元素不能使用两遍

首先可以尝试一下暴力方法，就是循环查找吧。上代码

class Solution(object):

def twoSum(self, nums, target):

""":type nums: List[int]:type target: int:rtype: List[int]"""

if not nums or len(nums) == 0:

return;

#先要判断一下 nums 是不是空。 都是必要的

for i in range(len(nums)):

for j in range(i+1,len(nums)):

if(nums[i] + nums[j] == target):

return [i,j]

#依次遍历nums直到找到 两个数相加等于target

return;

然后这种方法不用说，虽然可以通过，但是太直接了吧

leetcode 怎么会有这么简单的算法题呢是不是。

那当然要降低一下时间复杂度了，现在是O(

)嘛

如何能降低时间复杂度呢

以上已经是非常直接的解法了。

那么再降低时间复杂度的话

就需要用空间来换了

所以还有一种O(N)的解法就是用空间来换取时间。

class Solution(object):

def twoSum(self, nums, target):

""":type nums: List[int]:type target: int:rtype: List[int]"""

if not nums or len(nums) == 0:

return;

dict = {}

#新建一个字典 字典的key 是target - 数组里面 一个数， value 是这个数的Index，

#只要新遍历到的数发现了在dict中，则返回这两个index

for i in range(len(nums)):

if nums[i] in dict:

return [dict[nums[i]], i]

dict[target - nums[i]] = i

return;

这种方法只需要一次遍历。时间复杂度就是O(N)了， 空间复杂度也O(N)

那么这道题做到这里就基本上做完了。

如果说发现第二种做法，你需要一段时间来理解一下。

或者比如今天看完第二天不能直接把这个解法敲出来

那应该算是基础比较薄弱了

在这里推荐大家一个当年我看编程的入门书吧。

有兴趣的同学可以研究研究，但是不适合用来准备找工作哈。

适合自学研究研究。我个人是比较喜欢像这种

比较不那么功利性质的书

要是着急就要找工作了的话还是推荐剑指offer哈哈哈

c++就直接写dict 的做法了。

C++代码：

class Solution {

public:

vector twoSum(vector& nums, int target) {

//记得判断一下空！！！ if(!&nums || nums.size() == 0)

cout<< "llll"<< endl;

vectorresult;

unordered_mapdict;

int point1;

int point2;

for(int i = 0; i< nums.size(); i++){

if(dict.count(target - nums[i]) !=0){

point1 = i;

point2 = dict[target - nums[i]];

break;

}

else{

dict[nums[i]] = i;

}

}

result.push_back(point1);

result.push_back(point2);

return result;

}

};

养成一个习惯，写任何的函数功能的时候

都判断一下输入会不会有问题

在工作中

也是被这个坑过了

然后就是如果加上这一句

面试时候是有加分的哈

欢迎大家讨论更多的解法

喜欢的朋友可以点赞

我会坚持更新的。