【LeetCode题解---1】Two Sum
今日金句
发表于苍穹盛夏
查看:13500回复:135
“Bad programmers worry about the code. Good programmers worry about data structures and their relationships.”
（低水平程序员总在考虑代码，高水平程序员总在考虑数结构及其之间的关系）
1
题目
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0, 1].
地址 https://oj.leetcode.com/problems/two-sum/ 2
词汇学习
integers 整数 indices 指数 add up 加起来
specific 具体 target 目标 assume 承担
exactly 究竟 solution 解 解答
3
惊人而又蹩脚的中文翻译
给定一个整数数组 一个目标整数 求出这个整数值是数据中的哪两个元素的和 返回下标组成的数组
4
代码实现-java
01
解法一
暴力搜索解法：暴力搜索的方法是遍历所有的两个数字的组合，然后算其和。
代码如下：
public static int[] twoSum(int[] nums, int target) {
int[] array = new int[2];
for (int i=0;i<nums.length;i++) {
for (int j=1;j<nums.length - 1;j++) {
if (nums[i] + nums[j] == target) {
array[0] = i;
array[1] = j;
break;
}
}
}
return array;
}02
解法二
遍历一个数字，那么另一个数字呢，我们可以事先将其存储起来，使用一个HashMap，来建立数字和其坐标位置之间的映射，我们都知道HashMap是常数级的查找效率，这样，我们在遍历数组的时候，用target减去遍历到的数字，就是另一个需要的数字了，直接在HashMap中查找其是否存在即可，注意要判断查找到的数字不是第一个数字，比如target是4，遍历到了一个2，那么另外一个2不能是之前那个2，整个实现步骤为：先遍历一遍数组，建立HashMap映射，然后再遍历一遍，开始查找，找到则记录index。
代码如下：
public static int[] twoSum2(int[] nums,int target) {
int[] array = new int[2];
//
for (int i=0;i<nums.length;i++) {
map.put(nums[i],i);
}
for (int i=0;i<nums.length;i++) {
//
//
if (map.containsKey(temp) && map.get(temp) != nums[i]) {
array[0] = i;
array[1] = map.get(temp);
break;
}
}
return array;
}03
解法3
结题思路同解法2 但是可以爸两个for循环做合并 使得代码更加简洁
代码如下 ：
public static int[] twoSum3(int[] nums,int target) {
int[] array = new int[2];
Map<Integer,Integer> map = new HashMap<>(nums.length);
for (int i=0;i<nums.length;i++) {
//
array[0] = map.get(target - nums[i]);
array[1] = i;
break;
}
map.put(nums[i],i);
}
return array;
}5
代码实现-python
01
解法一
同上述java版本暴力解法一致，直接使用for循环
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
towSum=[]
for i in range(len(nums)):
onenum=nums[i]
twonum=target-nums[i]
if twonum in nums:
j=nums.index(twonum)
if i!=j:
towSum.append(i)
towSum.append(j)
return towSum此方法循环时间都很长： 按照官方代码来说，还是采用字典更好
02
解法二
采用字典方式进行计算
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
#创建字典一：存入nums[i],i
num_dict={num[i]: i fori in range(len(nums))}
#创建字典二：存入i:target-nums[i]
num_dict2={i:target-num[i] fori in range(len(nums))}
towSum=[]
for i in range(len(nums)):
j=num_dict.get(num_dict2.get(i))
if (j is not None) and (j!=i):
towSum=[i,j]
break
return towSum闲谈几句：
欢迎大家开启LeetCode刷题的旅程，这将是一段漫长而又艰辛的旅程，这是一条攀登珠穆朗玛的皑皑雪山路，这是无比残酷的修罗场。但请不要害怕，在 船长Grand苍穹盛夏博主的带领下，必将一路披荆斩棘，将各位带到成功的彼岸，不过一定要牢记的是，不要下船，不要中途放弃，要坚持，要自我修炼，不断成长！那么，起航吧～这道Two Sum的题目作为LeetCode的开篇之题，乃是经典中的经典，就像英语单词书的第一个单词总是Abandon一样，很多没有毅力坚持的人就只能记住这一个单词，所以通常情况下单词书就前几页有翻动的痕迹，后面都是崭新如初，道理不需多讲，鸡汤不必多灌，明白的人自然明白。
以上代码会同步更新在本人的Github和CSDN上
Github地址：https://github.com/Bylant/LeetCode
CSDN地址：https://blog.csdn.net/ZBylant