[数据结构与算法]LeetCode 1. 两数之和

1. 两数之和

Ideas

算法：迭代
数据结构：哈希表

Code

法一：单次哈希

时间复杂度：O(N)
空间复杂度：O(N)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = {}
        for i in range(len(nums)):
            if target - nums[i] in dic:
                return [dic[target - nums[i]], i] # 如果目标值在dict中，则返回目标值在dict中的索引和当前值的索引
            else:
                dic[nums[i]] = i # 如果目标值不在dict中，在dict中将当前值位置更新为索引

法二：暴力枚举

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

C++

#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
		unordered_map<int, int> hash_table; // 初始化哈希表
		for (int i = 0; i < nums.size(); i++) {
			auto flag = hash_table.find(target - nums[i]);
			if (flag != hash_table.end()) {
				return {flag -> second, i};
			}
			hash_table[nums[i]] = i;		// 注意这行代码的位置，必须在 if 判断完之后执行 
		}
		return {};
    }
};