Leetcode第⼀题：两数之和（3种语⾔）Leetcode第⼀题：两数之和
给定⼀个整数数组 nums 和⼀个⽬标值 target，请你在该数组中出和为⽬标值的 两个 整数。
你可以假设每种输⼊只会对应⼀个答案。但是，你不能重复利⽤这个数组中同样的元素。
⽰例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
标注：仅在Python解法做详细分析，c++与java如⽆特别需要注意的地⽅不做分析。
⼀、Python解法
解法2，3参考了
解法1：暴⼒搜索
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
#对nums每个元素循环
for i in range(len(nums)):
#从nums[i]的下⼀个开始
for j in range(i+1,len(nums)):
#如果到了就返回值
if nums[i]+nums[j]==target:
return i,j
分析：代码⼗分简单，就是⾸先⽤i在数组⾥循环⼀轮，在每个i循环下，去从剩下的元素target-nums[i]的值。如果到了，就return i，j两个数。（程序假设⼀定可以的到）
来看看运⾏结果：
可以看到效率是⼗分低的，主要原因就是⽤了两个for循环，时间复杂度是O(n )。
解法2：⼀次for 循环
⼀开始犯了⼀个⼩错误的代码
class  Solution :
def  twoSum (self , nums , target ):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
#直接在i ⼀个⼀个循环的时候，直接判断target-nums[i]在列表⾥吗，在的话⽤list.index()获取索引，⽤了⼀次for 循环。很棒。
for  i in  range (len (nums )):
if  target -nums [i ] in  nums :
return  i ,nums .index (target -nums [i ])
2
此代码的运⾏问题在于：
我们可以看到，忘记了⼀个元素只能⽤⼀次的规矩，因此做⼀个判断即可。
修改版：
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for i in range(len(nums)):
if target-nums[i]in nums:
#增加了返回的两个数下表不能相同的判断
if i!=nums.index(target-nums[i]):
return i,nums.index(target-nums[i])
可以看到：速度上升了好⼏倍。效果还不错。但是通过查看官⽅解答参考了知道还有⼀种更快的⽅法----基于hash table的解决⽅法。
解法3：基于Python字典查
关于hash table(哈希表)，简单来说就是存有键值对key,value的⼀种数据结构，对于熟悉Python的⼈来说，常见的字典就是⼀种hash table。它的查速度是很快的，可以理解为O(1)。所以这⾥相当于在解法2的基础上做了⼀个改进。解法2 是在空间不变的前提下，在i循环时，直接在列表⾥查是否含有target-nums[0]的元素，⽽列表的查速度是远不如hash table。所以解法三的关键就在于，查的任务在字典中进⾏⽽不在list中进⾏(有待商榷)
代码：
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
#遍历⼀个i，就把nums[i]放在字典⾥。之后i不断相加，总会碰到
#target - nums[i]在字典⾥的情况。碰到的时候return即可。这⾥注意到先return的是dict[a]，再是当前的i，原因就是dict⾥存的value都是以前遍历过的i，所以它⽐当前的i⼩，按从⼩到⼤的顺序所以这样排。
dict={}
for i in range(len(nums)):
a = target - nums[i]
if a in dict:
return dict[a],i
else:
dict[nums[i]]= i
运⾏结果：
可以从代码中看到，解法3就是把需要查的target-nums[i]从解法2中list变成了dict⽽已，但结果提⾼的⼗分可观。但要注意的是，这⾥⽤空间与实践做了⼀个tradeoff，也就说解法3虽然快了很多，但是需要的空间增加了⼀个新的dict。
这也给我们了⼀个提⽰：以后如遇到类似的需要遍历查的元素时，不妨参照本例，利⽤hash table查。
⼆、Java解法
解法2，3参照了官⽅解法
以及
Pythonliast与java数组区别
关于hashmap数据类型
解法1：暴⼒搜索
代码：
public int[]twoSum(int[] nums,int target){
int[] a =new int[2];
for(int i=0;i<nums.length;i++){
for(int j=i+1;j<nums.length;j++){
if(nums[i]+nums[j]==target){
a[0]= i;
a[1]= j;
//return new int[] {i,j};
}
}
}
return a;
}
}
这⾥不作特别说明。只想提及的是关于return new int[] {i,j}的些许解释。这种写法是官⽅解读给出的。参考，可以知道这是函数输⼊参数或者充当返回值的⼀种⽅式。
同时，官⽅解法在类的最后会throw⼀个异常，若将其删除会报错，因为throw也是return的⼀种替代形式。(就是说即使这个类在开头就说了不是void的，要返回⼀个int[]或者其他的东西，但是在最后抛出⼀个异常语法上是符合的。)对于本例，执⾏着就会从if下的return离开程序，所以不会抛出异常的。
解法2：两次for循环（两遍hashmap）
在这⾥和Python的3种解法做⼀个⽐较。可以看到两种语⾔的解法1是完全相同的。但是解法2上，会有⼀些区别。之后解法3⼜是完全相同的。为什么解法2会和Python解法2有区别呢？
先回顾下Python解法2：通过i循环列表，直接判断target - nums[i]是否在列表⾥，在的话，就直接返回i，与list.index(target-nums[I])。这⾥我们⽤了Python内置函数index。可以⽅便的获取到索引，⽽对于java的数组，并没有那么⽅便获取数组元素索引的函数。，从中可以知道java对于数组有⼀个binarySearch的查⽅法，⽽它本⾝就是⽤⼆分法查实现的，所以只适⽤于有序数组。同时若再⽤⼀次for循环获取索引，得不偿失。那不如多⽤⼀次for循环把索引与数值⼀⼀对应起来，⽤类似Python字典的⽅式，这样查的更快-----hashmap
代码：
class Solution {
public int[]twoSum(int[] nums,int target){
int[] b =new int[2];
HashMap<Integer,Integer> map =new HashMap<Integer,Integer>();
for(int i=0;i<nums.length;i++){
map.put(nums[i],i);
}
for(int j=0;j<nums.length;j++){
int a = target - nums[j];
ainsKey(a)&& j!=(a)){
b[0]= j;
b[1]= (a);
return b;
//return new int[] {(a)};
}
菜鸟教程python3100题}
return b;
}
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。