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 = [, , , ], target = , Because nums[] + nums[] = + = ,
return [, ].
这道题最简单的解决方法当然是双循环找到符合要求的结果。
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{nums[i], nums[j]};
}
}
}
return null;
}
首先这样写在LeetCode上可以通过，刚才试了一下，但是这个题在笔试中出现的话，应该是这个公司不想招人或者是不想通过笔试招人。
如果是在面试中出现，面试官肯定让你写出时间复杂度更低的代码，因为这个代码的时间复杂度O(n²)。下面介绍另一种解法：
public int[] twoSum(int[] nums, int target) {
if (nums == null) {
return null;
}
HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
if (hashMap.containsKey(nums[i])) {//当map中有值需要当前值时，说明找到结果。
return new int[]{hashMap.get(nums[i]), i};
}
hashMap.put(target - nums[i], i);
//存入当前值所需要的数值，比如target为5，当前值为1，他需要4，才能得到目标值。
}
return null;
}
以空间换时间HashMap底层是hash表，查找的时间复杂度为O(1)，所以上述代码的时间复杂度为O(n)，额外空间复杂度为O(n)。以空间换时间。