给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
1
2
3
4
| 给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
|
解题思路
傻瓜式想法：遍历两次，求和（去除重复的元素，位置不同的相等元素可以进行计算）
力扣内心OS：你这样的时间复杂度能过算我输！！！
😯：就这，略施小计：空间换时间之术
首先，遍历一遍数组将数组的值放入 Map 中，然后再遍历一次，将 target - 取到的值，但是要注意不能仅仅判断是
否存在这个值，因为可能会出现下面这种情况：target = 4，该数组中就只有一个 2，这样就会出错。所以还要判断
取到的值还不能是第一次的元素。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
hashMap.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int temp = target - nums[i];
if (hashMap.containsKey(temp) && hashMap.get(temp) != i) {
res[0] = hashMap.get(temp);
res[1] = i;
break;
}
}
return res;
}
}
|