[LeetCode] 1. Two Sum

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 = 9Output: [0,1]Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:Input: nums = [3,2,4], target = 6Output: [1,2]
Example 3:Input: nums = [3,3], target = 6Output: [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?

两数之和。

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
你可以按任意顺序返回答案。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

暴力解是O(n^2)级别的复杂度，一定会超时。为了不超时，我们使用 hashmap 记录每个元素和他的下标。找的时候是在找 hashmap 里是否存在能组成 target 的另一个数字 target - nums[i]。
LC里面有一部分题目也是需要通过 hashmap 或者 two pointer 来加快运行速度的。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
	public int[] twoSum(int[] nums, int target) {
		// corner case
		if (nums == null || nums.length < 2) {
			return new int[] { -1, -1 };
		}

		// normal case
		// <element, index>
		HashMap<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < nums.length; i++) {
			int complement = target - nums[i];
			if (map.containsKey(complement)) {
				return new int[] { map.get(complement), i };
			} else {
				map.put(nums[i], i);
			}
		}
		return new int[] { -1, -1 };
	}
}

JavaScript实现

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
	let map = {};
	const len = nums.length;
	for (let i = 0; i < len; i++) {
		let cur = nums[i];
		let complement = target - cur;
		if (map[complement] !== undefined) {
			return [map[complement], i];
		}
		map[cur] = i;
	}
};