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)

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)

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

也就是先绑定下标和数值对数组进行排序，再利用双指针一左一右相加进行比较，最终得出所需要的原来的下标。

时间复杂度 O(nlgn)，空间复杂度O(n)。 分别因为排序和存储下标。