TwoSum

题目

TwoSum
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
• 是否有序未知
• \(\mathcal{target}=\mathcal{num[idx1]}-\mathcal{num[idx2]} | idx1 \ne idx2\)
• 一定有解
• 同样元素不能用两次

理解例子

• nums = [2, 7, 11, 15]
• target = 9
• 对于 idx = 0. nums[idx] = 2
• 需要找到 nums[idx2] = target - nums[idx] –> 7
• nums[idx2] = 7 idx2 = 1
• [0, 1]

思路

• 例子中，找到 target-nums[idx] 并不够，还要找到 target-nums[idx] 对应的index
• 因此需要建立 index 和 value 的关系
• 关系建立好之后
• 对于每一个元素 idx ，查找 target-nums[idx] 以及对应的index
• 找到就返回结果，未找到返回空
• 出入参合法性判断
• 需要的数据结构：
• unordered_map<int,int> 哈希表，分别存放 value,index

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        if(nums.empty()) return {};
        unordered_map<int,int> map_;

        for (int i = 0; i < nums.size(); i++) {
            if (!map_.count(nums[i])) {
                map_[nums[i]] = i;
            }
            int num_to_find = target-nums[i];
            if (map_.count(num_to_find) && map_[num_to_find] != i) {
                return {i, map_[num_to_find]};
            }
        }
        return {};
    }
};

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var dict = [Int:Int]()
        for (i, num) in nums.enumerated() {
            if let lastIdx = dict[target - num] {
                return [lastIdx, i]
            }
            dict[num] = i
        }
        return []
    }
}

时间复杂度

每个元素只遍历一次，因此是线性时间 \(\mathcal{O(n)}\)

空间复杂度

额外申请了和数组长度一样的哈希表，因此空间复杂度也为 \(\mathcal{O(n)}\)