[TOC]
题目
给定一个整数数组nums和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
说明
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回[0, 1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解答
一般思路
当然是双层循环了，简单，直观，缺点就是时间复杂度是
public static String doubleFor(int[] nums, Integer target) {
// 第一层循环
for (int i = 0; i < nums.length; i++) {
// 这里获取需要匹配到的值
int cc = target - nums[i];
// 第二层循环
for (int j = i + 1; j < nums.length; j++) {
if (cc == nums[j]) {
return i + " && " + j;
}
}
}
return "没有合适的值";
}
优化思路
我们可以看到，第二层循环其实是在寻找和target - num[i]相等的值
- 问题转化为：
如何在一组数中快速查找一个数
-
解决方法：当然是使用
HashSet查找最快，但是我们的数字可能重复，而且我们也需要数的下标，所以可以使用HashMap来优化 -
优化后的代码：
public static String buildMap(int[] nums, Integer target) {
// 这里要使用可以存储多个value的Map,因为数字是可能重复的 这里使用的是 commons.collections4 中的集合类
MultiValuedMap<Integer, Integer> map = new HashSetValuedHashMap<>();
// 循环构建Map
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int cc = target - nums[i];
if (map.containsKey(cc)) {
// 这里要检查是否是重复的数字
final int currentIndex = i;
Optional<Integer> findNumOpt = map.get(cc).stream().filter( x -> currentIndex != x).findFirst();
if (findNumOpt.isPresent()) {
return "[ " + i + " ，" + findNumOpt.get() + " ]";
}
}
}
return "没有合适的值";
}
- 效率比较：
public static void main(String[] args) {
// 定义随机出的最大数
int maxNum = 1_0000_0000;
// 定义随机出的数的数量
int num = 100_0000;
// 获取target
Integer target = RandomUtils.nextInt();
List<Integer> integers = Lists.newArrayList();
for (int i = 0; i < num; i++) {
integers.add(RandomUtils.nextInt(0, maxNum));
}
// 随机数去重复
int[] distinctIntegers = integers.stream().distinct().mapToInt(Integer::intValue).toArray();
System.out.println("参与的总数量：" + distinctIntegers.length);
long firstStartTime = System.currentTimeMillis();
String s = doubleFor(distinctIntegers, target);
long firstEndTime = System.currentTimeMillis();
long firstTime = firstEndTime - firstStartTime;
System.out.println("方式执行时间为:" + firstTime + "毫秒");
System.out.println(s);
long secondStartTime = System.currentTimeMillis();
String s1 = buildMap(distinctIntegers, target);
long secondEndTime = System.currentTimeMillis();
long secondTime = secondEndTime - secondStartTime;
System.out.println("第二种方式执行时间为:" + secondTime + "毫秒");
System.out.println(s1);
}
============================
参与的总数量：995034
doubleFor方式执行时间为:110492毫秒
没有合适的值
buildMap方式执行时间为:1163毫秒
没有合适的值
=============================
只能讲是天差地别。。。。
为什么要先建立Map，如果输入特别多怎么半
- 问题
我们在优化的算法中，先循环了一遍，创建
Map，所以在某些情况下，其实还不如双层循环速度快。我们之前是判断一个数是否在整个输入的数组中存在，这是没问题的，但是我们要先循环一遍数组构建Map，构建Map也是需要消耗性能的，所以能不能把构建Map的动作延迟
- 解决办法：
我们之前是判断一个数是否在整个输入的数组中存在，我们能不能在循环到某个num时，判断target-num是否在之前的数中，这样我们最坏的情况，只需要循环一次数组就可以了。
public static String lazyMap(int[] nums, Integer target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int cc = target - nums[i];
if (map.containsKey(cc)) {
return "[ " + map.get(cc) + " ，" + i + " ]";
} else {
map.put(nums[i], i);
}
}
return "没有合适的值";
}
- 效率比较
### 加了数字，方便比较
doubleFor方式执行时间为:1336毫秒
[ 3547 ，77735 ] values:(292335 , 6314670)
buildMap方式执行时间为:1211毫秒
[ 3547 ，77735 ] values:(292335 , 6314670)
lazyMap方式执行时间为:18毫秒
[ 14265 ，76774 ] values:(2103266 , 4503739)
### 这里第二种方法是最慢的，是有这种可能的，运气好，前几个数就能匹配到合适的值
参与的总数量：994980
doubleFor方式执行时间为:142毫秒
[ 512 ，394240 ] values:(1049692 , 7348148)
buildMap方式执行时间为:2466毫秒
[ 512 ，394240 ] values:(1049692 , 7348148)
lazyMap方式执行时间为:6毫秒
[ 9201 ，34636 ] values:(4261592 , 4136248)
###
参与的总数量：995028
doubleFor方式执行时间为:1525毫秒
[ 4392 ，434770 ] values:(2052096 , 4910043)
buildMap方式执行时间为:1053毫秒
[ 4392 ，434770 ] values:(2052096 , 4910043)
lazyMap方式执行时间为:6毫秒
[ 10162 ，20333 ] values:(5509997 , 1452142)
###
参与的总数量：994959
doubleFor方式执行时间为:2915毫秒
[ 7605 ，36196 ] values:(188646 , 380034)
buildMap方式执行时间为:1576毫秒
[ 7605 ，36196 ] values:(188646 , 380034)
lazyMap方式执行时间为:12毫秒
[ 7605 ，36196 ] values:(188646 , 380034)
###
看来第三种方法真的是吊打。。。
其他语言解法
1. JS
function findTwoNumber(arr, target) {
// ES6里面才支持Map 和 Set
var numMap = new Map()
for (var i = 0; i < arr.length; i++) {
var num = target - arr[i]
if (numMap.has(num)) {
return "[ " + numMap.get(num) + " , " + i + " ]";
} else {
numMap.set(arr[i], i);
}
}
return null
}
2. Python
def find_two_number(nums, target):
num_dict = {}
for index in range(0, len(nums)):
num = nums[index]
cc = target - num
if num_dict.get(cc) is not None:
return "[ " + str(num_dict.get(cc)) + " : " + str(index) + " ]"
else:
num_dict[num] = index
return "没有合适的值"
网友评论