给出一个数组和一个目标值,让你在该数组中找出和为目标值的两个数,并且这两个数在数组中的下标不同。
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1]
简单
首先,我们能够很自然地想到暴力遍历数组的这个方法,两层遍历,第一层确定第一个数,第二层确定第二个数,从而完成题目的要求。
说句题外话,“暴力”一词在算法领域表示“穷举、极低效率的实现”,可能就是源于这个英文词(Brute-Force,蛮力攻击)。
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[i] + nums[j] == target)
return new int[]{i,j};
}
}
throw new IllegalArgumentException("No two sum solution");
}
}
笔试的时候如果遇到不太会的题,就暴力。不过两次遍历的时间复杂度是
。
时间复杂度,在算法领域是一个非常重要的概念,https://tobebetterjavaer.com/collection/time-complexity.html了解。
的时间复杂度实在是太不理想了,效率还是太低,在所有 Java 提交中只能击败不到 22% 的用户。
我们能不能优化一下呢?
观察第二个循环,我们是从每个i
的后面的数中寻找一个与之相加能够凑成目标值target
的。
那我们就反过来想,能不能判断每个i
前面的数是否存在与之相加能够凑成目标值target
的呢?
可能你会脑袋一热写出下面这样的代码:
class Solution{
public int[] twoSum(int[] nums,int target){
for(int i = 0;i < nums.length;i++)
for(int j = 0;j < i;j++)
if(nums[i] + nums[j] == target)
return new int[]{i,j};
throw new IllegalArgumentException("No two sum solution");
}
}
但是这样的算法时间复杂度和之前相比根本没有变化。
再想一下,每一个i
前面的数我们之前访问过,所以我们可以用一个HashMap
来记录每一个i
前面的数的出现情况以及坐标,这样子就可以快速地查到它前面的数了。
class Solution{
public int[] twoSum(int[] nums,int target){
HashMap<Integer,Integer> map = new HashMap<>();
for(int i = 0;i < nums.length;i++){
int sub = target - nums[i];
if(map.containsKey(sub))
return new int[]{i,map.get(sub)};
map.put(nums[i],i);
}
throw new IllegalArgumentException("No two sum solution");
}
}
时间复杂度:
空间复杂度:
这次结果就不一样了,打败了 70.02% 的选手。
001-01.png