1. Two Sum

1. Two Sum (easy) 两数之和

题干

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6 Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6 Output: [0,1]

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

解题思路

暴力解法

外层循环套内层循环，内层循环的范围，是外层循环当前元素下一个元素到数组末尾。判断只要两个循环中的元素相加等于target即可返回。

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

技巧解法

第一个元素根据循环所得，是已知的，此时时间复杂度已经到了O(n)。如果要降低时间复杂度，追求比O(n^2)小，寻找另外一个元素不能再循环。

根据条件：

• 两数之和是target，可以得到另外一个数
• 有且只有一对元素

那问题就变成了在O(n)的基础上，得到了一个数的值（target-第一个循环得到的元素），来找它的索引。这可以用元素的值当key，元素的索引当value，组成的hash来解决。

因为题目中没说元素不可重复，所以创建hash的时候还要考虑元素值重复的情况

我的答案

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashed_nums: Dict[int, int] = {}
        for i in range(len(nums)):
            if not hashed_nums.get(nums[i]):
                hashed_nums[nums[i]] = [i]
                continue
            hashed_nums[nums[i]].append(i)

        result = []
        for left_idx in range(len(nums)):
            left = nums[left_idx]
            right = target - left
            for right_idx in hashed_nums.get(right, []):
                if right_idx > left_idx:
                    result = [left_idx, right_idx]
                    return result
        return result