题目：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
解法：
- 直接遍历法
遍历所有元素，对于特定x寻找是否有target-x与之匹配。
class Solution {
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[j] == target - nums[i]){
return new int[] {i,j};
}
}
}
throw new IllegalArgumentException("No two sum");
}
}
时间复杂度：O(n^2) ，空间复杂度：O(1)
- 两遍哈希表
利用哈希表进行查找计算，牺牲空间节省时间。
第一遍先将每个元素的值和索引存入哈希表中。
第二遍对于每个元素在哈希表中查找是否有满足条件的匹配元素存在。
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++){
map.put(nums[i],i);
}
for(int i=0;i<nums.length;i++){
int complement = target - nums[i];
if(map.containsKey(complement) && map.get(complement)!=i){
return new int[] {i,map.get(complement)};
}
}
throw new IllegalArgumentException("No two sum");
}
}
时间复杂度：O(n)，空间复杂度：O(n)
- 一遍哈希表
将元素插入哈希表之前，先检查表中是否存在匹配元素，如果有匹配那么返回结果，这样只需遍历一次哈希表，节省时间。
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<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};
}
map.put(nums[i],i); //先检索后插入可以避免返回相同元素
}
throw new IllegalArgumentException("No two sum");
}
}
时间复杂度： O(n)，空间复杂度：O(n)
