LeetCode算法-1.Two Sum [easy]

Question:

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].

Solution:

方法1：暴力法：

设置两层循环，从正面解决问题，直接判断两数之和。
时间复杂度：$O(n^2)$ 执行用时：6692 ms 内存消耗：14.2 MB

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if(nums[i] + nums[j] == target):
return [i,j]

python函数注释：参数后加冒号表示参数类型，函数后加箭头表示返回值的类型。 $nums:List[int]$ 表示参数及其类型，末尾的->List[int]则用于注释函数的返回值类型。这两处的参数类型不用写也是可以的，属于注释。可以在函数中用三引号的方式来写。

同样是暴力解决，Java的执行速度就快很多。执行用时：210 ms 内存消耗：39.7 MB

class Solution {
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 = new int[]{i, j};
}
}
}
return a;
}
}

方法2：寻差

既然要得到两数相加为目标值的两数下标，为了降低复杂度，我们可以只用一层循环，然后寻找目标值与当前值的差是否存在于数组中，并保存该差的下标(两数不能是nums中的同一个元素)。
时间复杂度：$O(n)$ 执行用时 :1008 ms 内存消耗 :14.1 MB
经查询，list中index时间复杂度是O(1)。List中内置函数的时间复杂度

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
temp = target - nums[i]
if temp in nums and nums.index(temp) is not i:
return [i, nums.index(temp)]

为了简化以上代码，搜索差的位置时，只在i之后的list中查找，所以对list做切片。发现不如用nums[:i]表示方便。
执行用时 :972 ms 内存消耗 :14.3 MB 效果不大

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
j = -1
temp = target - nums[i]
if temp in nums[i+1:]:
j = nums[i+1:].index(temp)
return [i, j+i+1]

方法3：哈希-字典

将list中所有元素及其index建立一个相应的dict，直接可以映射出target-num的下标，而无需消耗时间去查找该值的位置。
执行用时 :56 ms 内存消耗 :15.5 MB

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
index = {}
for i, num in enumerate(nums):
index[num] = i
for i, num in enumerate(nums):
j = index.get(target - num)
if j is not None and j != i:
return [i,j]

类似于方法2的第二段方法，不需要将所有元素都放入dict之后才处理，num1之前的list中找是否存在target-num1，如果不存在，将num1放入dict，进行下一次寻找；如果存在，则分别输出num2，num1的位置。

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
index = {}
for i, num in enumerate(nums):
if index.get(target - num) is not None:
return [index.get(target - num),i]
index[num] = i

惊了！执行用时 :32 ms, 在所有 Python3 提交中击败了98.49%的用户
内存消耗 :14.7 MB

写在最后的话：为了熟悉语言语法，学习算法，如何优化代码，如何转换固有思路，所以开始一步步探索之路。这道题是LeetCode的第一题，很简单，也让我稍微复习了一下Python及其特性。

最后

以上就是英勇火为你收集整理的LeetCode算法-1.Two Sum [easy]的全部内容，希望文章能够帮你解决LeetCode算法-1.Two Sum [easy]所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。