【例题】给定一个整数数组nums 和一个目标值 target，请在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
*可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
看到题的第一眼想到的便是暴力解法，代码如下：
public static Object[] test1(int[] nums,int num){
long t1 = System.currentTimeMillis();
for(int i = 0; i < nums.length; i++){
for(int j = i+1; j < nums.length; j++){
if(nums[j] + nums[i] == num){
long t2 = System.currentTimeMillis();
long t3 = t2 - t1;
//返回两个数组下标及所用时间
return new Object[]{i,j,t3};
}
}
}
long t2 = System.currentTimeMillis();
return new Object[]{"No sulution",t2-t1};
}
时间复杂度为O(n^2)，空间复杂度为O(1)。
当数据量小于一万时，运行没有任何卡顿，但当处理大数据量时，速度明显变慢，于是就采用hashmap的方式比较了一下：
public static Object[] test2(int[] nums, int num) {
//时间戳
long t1 = System.currentTimeMillis();
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int tmp = num - nums[i];
//判断map中是否包含键名tmp
if (map.containsKey(tmp)) {
long t2 = System.currentTimeMillis();
//返回两个数组下标及所用时间
return new Object[] { i, map.get(tmp), t2-t1 };
}
map.put(nums[i], i);
}
long t2 = System.currentTimeMillis();
return new Object[]{"No sulution",t2-t1};
}
时间复杂度为O(n)，空间复杂度为O(n)。
数量小时，暴力解法与hashmap方式效率差不多，但当处理大数据时，使用containsKey方法会大大降低消耗。
快速/冒泡排序与map的containsKey方法之时间复杂度
原文：https://www.cnblogs.com/gonghuixin/p/12981927.html