1、两数之和
解法一：暴力循环
public int[] twoSum(int[] nums, int target){
for(int i =0; i< nums.length; i++){
for(int j =i+1; j<nums.length;i++){
if(nums[i] + nums[j] == target){
return new int[] {i,j};
}
}
}
return new int[0];//表示动态分配一个长度为0的int数组
}
- 时间复杂度是 O(n^2), n是数组中元素数量，最坏情况下数组中任意两个数都要匹配一次。
- 空间复杂度O(1)
解法二：哈希表
使用哈希表可以将寻找target-nums[i]的复杂度从O(N)降到O(1)
public int[] twoSum(int[] nums, int target){
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for(int i = 0;i<nums.length;i++){
if(hashtable.containsKey(target-nums[i])){
return new int{hashtable.get(target-nums[i]),i};
}
hashtable.put(nums[i],i);
}
return new int[0];
}
- 时间复杂度是 O(n),对于每一个元素 x，我们可以 O(1)地寻找 target - x;
- 空间复杂度O(n),为哈希表的开销。
