Sui Xin's Blog

[LeetCode]1. 两数之和（Two Sum）

Posted on In Disqus:

题目描述

给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

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

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

解题思路

  • 方法一：排序。将原数组的索引按照数组中数字大小排序，设置两个指针从排序索引数组两端开始向内移动，两数之和等于目标值则返回；
  • 方法二：哈希表。从头开始遍历数组，计算目标值与当前数的差，判断是否在哈希表中，若在，则返回这两个数字，否则将当前数添加到哈希表中。

代码

方法一：排序

Python 3.6

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        sorted_id = sorted(range(len(nums)), key=lambda x:nums[x])
        start, end = 0, len(nums) - 1
        while start < end:
            cur_sum = nums[sorted_id[start]] + nums[sorted_id[end]]
            if cur_sum > target:
                end -= 1
            elif cur_sum < target:
                start += 1
            else:
                return [sorted_id[start], sorted_id[end]]

执行用时 : 56 ms
内存消耗 : 14.2 MB

方法二：哈希表

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash_map;
        int lens = nums.size();
        for (int i = 0; i < lens; ++i) {
            auto it = hash_map.find(target - nums[i]);
            if (it != hash_map.end()) {
                return {it->second, i};
            }
            hash_map.emplace(nums[i], i);
        }
        return {};
    }
};

执行用时 : 12 ms
内存消耗 : 10.5 MB

Python 3.6

1
2
3
4
5
6
7
8
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for idx, i in enumerate(nums):
            difference = target - i
            if difference in hashmap:
                return [hashmap[difference], idx]
            hashmap[i] = idx

执行用时 : 56 ms
内存消耗 : 14.1 MB

参考

https://leetcode-cn.com/problems/two-sum/comments/9784

Related Posts