1. Two Sum

hashmap O(n) time O(n) space

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = {}
        for i, num in enumerate(nums):
            x = target - num
            if x in d:
                return [d[x], i]
            d[num] = i
        return [-1, -1]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = {}
        for i in range(len(nums)):
            x = target - nums[i]
            if x in d:
                return [d[x], i]
            d[nums[i]] = i
        return [-1, -1]

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

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        unordered_map<int, int> hm;
        for (int i = 0; i < n; ++i) {
            auto it = hm.find(target - nums[i]); // 为了解决数组中有相同数的问题，在每次插新数之前先进行查找，查找无果之后再插数，这样只需要扫描一遍即可
            if (it != hm.end()) {
                return {min(it->second, i), max(it->second, i)};
            }
            hm[nums[i]] = i;
        }
        return {-1, -1};
    }
};