描述

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].

---

分析

本题似乎很容易，遍历数组计算 nums[i] + nums[j] == target 即可，时间复杂度 $$\mathcal{O}(n^2)$$，空间复杂度为 $$\mathcal{O}(1)$$。

int* twoSum(int* nums, int numsSize, int target) {
    int *pos = malloc(sizeof(int) * 2);
    for (pos[0] = 0; pos[0] < numsSize; pos[0]++) {
        for (pos[1] = pos[0]+1; pos[1] < numsSize; pos[1]++) {
            if (nums[pos[0]] + nums[pos[1]] == target)
                return pos;
        }
    }
    return pos;
}

结果

Runtime: 136 ms, faster than 42.35% of C online submissions for Two Sum.
Memory Usage: 7.7 MB, less than 42.92% of C online submissions for Two Sum.

---

优化

在第一种方法中，判断 target - nums[i] == x 得到的 x 是否在数组中，需要对数组进行一轮遍历，时间复杂度为 $$\mathcal{O}(n)$$。如果能够更快速判断 x 是否在数组中，就可以缩短时间。我们可以通过空间换时间的方式，建立一个双向映射表，查表的时间开销为 $$\mathcal{O}(1)$$，极端情况下为 $$\mathcal{O}(n)$$，遍历数组的时间复杂度为 $$\mathcal{O}(n)$$，则可得到整体上的时间复杂度为 $$\mathcal{O}(n)$$，空间复杂度为 $$\mathcal{O}(n)$$。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_dict = dict()
        nums_bidict = dict()
        it = 0
        nums_size = len(nums)
        while it < nums_size:
            nums_dict[it] = nums[it]
            nums_bidict[nums[it]] = it
            it += 1
        it = 0
        values = set(nums)
        while it < nums_size:
            ret = target - nums_dict[it]
            if ret in values and it != nums_bidict[ret]:
                return [it, nums_bidict[ret]]
            it += 1

结果

Runtime: 44 ms, faster than 61.65% of Python3 online submissions for Two Sum.
Memory Usage: 15.9 MB, less than 5.08% of Python3 online submissions for Two Sum.