极客算法

LeetCode-1.两数之和(Two Sum)

2020-07-06

相信每个想刷leetcode的人,第一次打开网站,就从这道题开始的。

一起起航吧,Great Voyage.

1. 两数之和:

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

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

例如:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/two-sum/

Link:https://leetcode.com/problems/two-sum/

哈希

O(N)

遍历数组

如果在字典找到数字,则输出[字典下标,当前下标]

找不到答案,把当前的值放入字典(val -> index)

因为题目说有且只有一组答案,所以不用判断数组为空,返回值不存在的情况

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        map = dict()
        for i in range(len(nums)):
            val = target - nums[i]
            if val in map:
                return [map[val], i]
            else:
                map[nums[i]] = i

双指针

O(N*logN)

如果题目要求返回两个具体数字,可以先排序,然后使用双指针(start, end)

res = nums[start] + nums[end]

如果res < target, 则说明nums[start] + 最大的数都小于target, start的值太小了,应该start++

如果res > target, 则说明nums[end] + 最小的数都大于target, end的值太大了,应该end–

如果res = target, 则输出答案

class Solution(object):
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        start = 0
        end = len(nums) - 1
        
        nums.sort()
        
        while(start < end):
            res = nums[start] + nums[end]
            if res == target:
                return (nums[start], nums[end])
            elif res < target:
                start += 1
            else:
                end -= 1

–End–


评论

内容:
其他: