从零开始刷LeetCode

技术分享第一时间送达！

写在前面：

打卡刷LeetCode是受小詹的启发，自己也会在LeetCode刷题之前只是在网上做完就行了，今年在刷题的时候突然想做一下记录以后做回顾，之后每天都在有道云笔记做点记录，现在既然开了公众号索性就增加这个专栏。每天一题每一题都吃透，希望看到自己成长的点点滴滴。我会用两种语言来解决所有问题，专科的时候主修java现在本科自学python，所以两种语言都做一个尝试。

No.1两数之和

原题:

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

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

Java

首先想到遍历每个元素x，查找是否存在一个值与target-x相等的目标元素.。

public int[] twoSum(int[] nums,int target) {

for(int i =; i

for(int j = i +1; j

if(nums[j] == target - nums[i]) {

returnnew int[] { i,j };

}

}

}

throw new IllegalArgumentException("No

two sum solution");

}

在写代码之前没有考虑时间复杂度只是想着运行结果正确就行，后来看了看解答原来还可以用哈希表，又用哈希表的方法对运行时间复杂度进行优化。

两遍哈希表

publicint[] twoSum(int[] nums,inttarget) {

Map map = new HashMap();

for(inti =; i

map.put(nums[i],i);

}

for(int i =; i

int complement = target - nums[i];

if(map.containsKey(complement) &&

map.get(complement) != i) {

returnnewint[] {

i,map.get(complement) };

}

}

throw new IllegalArgumentException("No

two sum solution");

}

题目解答：

简单的实现使用了两次迭代。在第一次迭代中，我们将每个元素的值和它的索引添加到表中。然后，在第二次迭代中，我们将检查每个元素所对应的目标元素（target−nums[i]target - nums[i]target−nums[i]）是否存在于表中。注意，该目标元素不能是nums[i]nums[i]nums[i]本身！

一遍哈希

publicint[] twoSum(int[] nums,inttarget) {

Map map = new HashMap();

for(inti =; i

intcomplement = target - nums[i];

if(map.containsKey(complement)) {

returnnewint[] {

map.get(complement),i };

}

map.put(nums[i],i);

}

throw new IllegalArgumentException("No

two sum solution");

}

Python

用python写的时候思路跟java一样就是用一个嵌套循环把nums列表遍历两次。

class Solution:

deftwoSum(self,nums,target):

"""

:typenums: List[int]

:typetarget: int

:rtype: List[int]

"""

n =len(nums)

forxinrange(n):

foryinrange(x+1,n):

ifnums[y] == target - nums[x]:

returnx,y

break

else:

continue

有了之前的经验这种方法实现以后就开始考虑有没有更加优化的方法，用一个for循环，直接在里面查询target-nums[x]是否存在于nums列表中

classSolution:

deftwoSum(self,nums,target):

"""

:typenums: List[int]

:typetarget: int

:rtype: List[int]

"""

n =len(nums)

forxinrange(n):

a = target - nums[x]

ifainnums:

y = nums.index(a)

ifx == y:

continue

else:

returnx,y

break

else:

continue

感觉这两种方法差不多最后一种方法是从小詹那看到的。通过创建字典，将nums里的值和序号对应起来，并创建另一个字典存储目标值（Target）-nums的值，通过判断该值是否在nums内进行判断并返回其对应索引值

classSolution:

deftwoSum(self,nums,target):

"""

:typenums: List[int]

:typetarget: int

:rtype: List[int]

"""

num_dict =

print(num_dict)

num_dict2 =

print(num_dict2)

result = []

foriinrange(len(nums)):

j = num_dict.get(num_dict2.get(i))

if(jis not None)and(j != i):

result = [i,j]

break

returnresult

这就是今天的LeetCode刷题，只是做个学习记录，水平有限，大家多多包含，如果小伙伴有更好的想法可以在留言区分享。