[Leetcode 1] 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.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

解题思路

这是一道非常经典的面试题. 由于被面的太多, 现在一般会考察这道题的变种, 但是原题也还是经常出现在电话面试中, 或者被当做热身题.

这道题的O(n)解法是利用hash table来存储遍历过的元素, 对于当前的元素nums[i], 我们只需要判断target - nums[i]是否在哈希表中即可.

这道题可能会有follow up问能否不用额外空间, 那么就需要牺牲时间复杂度: 可以先排序, 然后用双指针两头扫遍历一遍即可, 这个方法此处不做赘述, 在Three Sum中会详细介绍.

示例代码 (cpp)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mapping;
        for (int i = 0; i < nums.size(); ++i) {
            if (mapping.count(target - nums[i])) {
                return {mapping[target - nums[i]], i};
            }
            mapping[nums[i]] = i;
        }
        return {-1, -1};
    }
};

示例代码 (python)

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        numsIdxDict = dict()
        for i in range(len(nums)):
            if (target - nums[i]) in numsIdxDict:
                return [i, numsIdxDict[(target - nums[i])]]
            numsIdxDict[nums[i]] = i

复杂度分析

时间复杂度: O(n) n为nums数组长度
空间复杂度: O(n)

归纳总结

面试中如果遇到这道题, 也不要太高兴直接开始写答案, 还是要好好分析思路, 问清楚要求, 比如是不是一定有解, 可能有多少解, 能不能用额外空间等等.