badEgg > leetcode - 两数之和

leetcode - 两数之和

2019-10-23

算法, leetcode

leetcode: 两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

对这道题一开始的思路是两套循环遍历找到为目标值的两个数，代码如下:

1
2
3
4
5
6
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]

循环遍历一遍，时间复杂度是n^2，可以通过但是非常常规且有时会超时

经过评论大佬的启迪，做一次排序后首尾递进显然更快，复杂度为排序的nlogn

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
		sorted_id = sorted(range(len(nums)), key=lambda k: nums[k])
    	head = 0
    	tail = len(nums) - 1
    	sum_result = nums[sorted_id[head]] + nums[sorted_id[tail]]
    	while sum_result != target:
        	if sum_result > target:
            	tail -= 1
        	elif sum_result < target:
            	head += 1
        	sum_result = nums[sorted_id[head]] + nums[sorted_id[tail]]
    	return [sorted_id[head], sorted_id[tail]]

这个速度明显会更快，但更花费空间

这样还不够，发现比较的都是数字，那么就有了更快的办法—hash字典

1
2
3
4
5
6
7
8
9
class Solution:
    def twoSum(self, nums, target):
        hashmap = {}
        for index, num in enumerate(nums):
            another_num = target - num
            if another_num in hashmap:
                return [hashmap[another_num], index]
            hashmap[num] = index
        return None

用hash字典大大增加了内存但是速度快到了n

还是图样图森破

这是第一天份的，明天继续= =