Leetcode-2sum-python

发表于 | 分类于 |

Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
Description

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(0, len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i]+nums[j]==target:
                    return [i, j]

初始版本的思路：
依次将两个数相加，由于题目中说明只存在一对答案，因此如果存在符合条件的两个下标，就是需要的答案。
测试未通过：
leetcode要求需要满足时间复杂度。

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def twoSum(self, nums, target):
        if len(nums) <= 1:
            return False
        buff_dict = {}
        for i in range(len(nums)):
            if nums[i] in buff_dict:
                return [buff_dict[nums[i]], i]
            else:
                buff_dict[target - nums[i]] = i

leetcode上提供的一种O(n)的python解法，使用字典, python字典采用hash方式。
解题思路：
建立一个字典，依次比较列表中的元素。如果字典的键中不存在该元素，就将target - nums[i]作为字典的键，并将对应的下标作为值；如果字典键中存在该元素，则说明字典中存在符合要求的对应元素，通过buff_dict[nums[i]]提取出另一个元素的下标。