sum of two numbers

(Updated: )
leetcode › algorithm

leetcode 1. 两数之和

两数之和

题目描述

方法1

双指针
时间复杂度O(nlogn)
空间复杂度O(1)
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
def twoSum(nums, target):
    nums = [(v, i) for i, v in enumerate(nums)]
    nums.sort()
    left, right = 0, len(nums) - 1
    while left < right:
        if nums[left][0] + nums[right][0] == target:
            return [nums[left][1], nums[right][1]]
        elif nums[left][0] + nums[right][0] < target:
            left += 1
        else:
            right -= 1
    return []

方法2

哈希表
时间复杂度O(n)
空间复杂度O(n)
代码如下：

1
2
3
4
5
6
7
def twoSum(nums, target):
    hashmap = {}
    for i, num in enumerate(nums):
        if target - num in hashmap:
            return [hashmap[target - num], i]
        hashmap[num] = i
    return []