LeetCode 01 两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

上来的第一个想法是双循环暴力求解，但是这样的时间复杂度是O(n^2)，所以需要思考一种更加优化的方式来解决这个问题。我们在双循环的内部循环中，其实就是在数组中寻找某个特定的值，因此使用查找方式更快的HashMap来替代数组，那么仅仅就只需要循环一遍，将时间复杂度降低到O(n)。我们要查找的是某个具体的值，那么Key就应该是具体的值，而题目最终要求返回对应的数组下标，那么Value就是对应的数组下标。

function twoSum(num_arr, target) {
	const num_map = {}
	
	for (let i = 0; i < num_arr.length; i++) {
		const target_value = target - num_arr[i]
		
		if (num_map.has(target_value)) {
			return [i, num_map[target_value]]
		}

		num_map[num_arr[i]] = i
	}
    return []
}

---

状态演示

遍历的数组，查看 target - current 是否在Map 中有对应的值

1. 如果 Map 中没有对应的值， 把当前的值作为 Key，对应的索引作为 Value
2. 如果 Map 中有对应的值就直接把当前的索引，以及对应 Map 中的 Value 返回

//存放记录的 Map
{}

[ 
	2, // <-  9 - 2 = 7，数组中没有，Map 存放 {2 , 0}
	11, 
	7,
	5
]

下一步

{ 2: 0}

[ 
	2, 
	11, // <-  9 - 11 = -2，数组中没有，Map 存放 {11 , 1}
	7,
	5
]

下一步

{ 2: 0, 11: 1}

[ 
	2, 
	11, 
	7, // <-  9 - 7 = 2，数组中有，返回 [2, 0]
	5
]