LeetCode *1.Two Sum (Python Solution)

86 阅读 0 评论 57 点赞

我是靠谱客的博主真实跳跳糖，这篇文章主要介绍LeetCode *1.Two Sum (Python Solution)，现在分享给大家，希望可以做个参考。

问题描述

Two Sum 原题链接
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.

给定一个整数数组，返回两个数字的索引，使它们的和为特定的target。

你可以假设每个输入确定只有一个解决方案，并且不可以重复使用相同的元素。

Python Solution

本文从两个角度来解读这道题，解法一是hashmap遍历数组，解法二是双指针，面试推荐第一种。

Solution 1 (hashmap)

复制代码

1
2
3
4
5
6
7
8
9
10
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict = {}
        for i, v in enumerate(nums):
            another = target - v
            if another not in dict:
                dict[v] = [another, i]
            else:
                return [dict[another][1],i]

只对数组进行一遍遍历。如果没有another，则在hashmap里创建，如果有，则输出目标。

时间复杂度O(n)，空间复杂度O(n)。

Solution 1 (double pointer)

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
nums = list(enumerate(nums))
        nums.sort(key = lambda x:x[1])
        i, j = 0, len(nums)-1
        while i < j:
            if nums[i][1] + nums[j][1] > target:
                j -= 1
            elif nums[i][1] + nums[j][1] < target:
                i += 1
            else:
                if nums[j][0] < nums[i][0]:
                    nums[j], nums[i] = nums[i], nums[j]
                return  nums[i][0],nums[j][0]
        return False