1、两数之和
两数之和
- 1、题目描述
- 2、解答思路
1、题目描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
2、解答思路
class Solution {
public int[] twoSum(int[] nums, int target) {
int len = nums.length;
// 按照规范，这里的HashMap应定义长度len-1
// key: nums[i] value: i
Map<Integer,Integer> hashTable = new HashMap<Integer, Integer>(len-1);
for(int i = 0;i<len;i++){
// 去哈希表中查找是否有target-nums[i]存在，若有则返回结果，否则将其存到哈希表中
if(hashTable.containsKey(target-nums[i])) {
// 无需定义一个新的变量，直接返回new的对象即可
return new int[] {i, hashTable.get(target-nums[i])};
}
hashTable.put(nums[i], i);
}
// 若不存在，则抛出异常或任意返回值
return new int[0];
}
}
- 时间复杂度：O(N)，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 O(1) 地寻找 target - x。
- 空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销。