前言
本系列将更新LeetCode题目刷题记录，每道题都强行向最优效率靠近，看看Java实现能快到什么程度
当然笔者也会分析LeetCode上已有的极限方案，大家也可以来一起讨论还有没有更好的优化方法
优化将从自己思考开始，伴随对评论中出现的解法借鉴，或者查阅其他资料
整个文章将展现所有笔者的思路，和完整优化过程
但今天这第一题的一篇文章写下来，我发现太花时间了，我只是把我曾经写过的代码拿出来，组织成文章，就写了一天，可能后续这个系列的更新就比较缓慢了
题目解读
给定一个整数数组 nums和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
上面这段是原LeetCode描述的题目
这个题目还是比较好理解的，这里解读一下后面两句话
-
“可以假设每种输入只会对应一个答案“
这句话的意思是，可以不用在意整组数据可能有多少种答案，找到其中的一种就可以返回结果
-
“数组中同一个元素在答案里不能重复出现“
这句话的意思是，不可以是自己加自己等于目标值，返回下标1和1
-
“可以按任意顺序返回答案“
这句话的意思是，比如找到的两个数下标为0和1，你可以返回1和0
ok除此之外就没什么可再说的了，下面就直接开始实现吧
实现
方案一、暴力匹配
这是最简单最容易想到的一种方式
外层循环挨个取出数组中元素，进入内存循环向后查找是否有相加等于目标值的
注意点：
- 最后一个元素就不用参与比较了，因为遍历倒数第二个就和他相加与目标值比较过了
- 内层循环从外层遍历到的元素后边开始即可，因为前面的也已经和它相加与目标值比较过了
很简单，直接上代码
public static int[] twoSum(int[] nums, int target) {
for(int i = 0;i<nums.length-1;i++){
for(int j=i+1;j<nums.length;j++){
if(nums[i]+nums[j]==target){
return new int[]{i,j};
}
}
}
return null;
}
- 执行用时：54ms > 25.34%
- 内存消耗：41.3MB > 88.04%
方案二、利用边界值判断，进行优化
这个是笔者自行思考后进行的优化
下面说一下思路
-
首先我们分析得出前边暴力匹配的时间复杂度
外层一定为n，内层是从n到1依次递减的
所以是一个n-1的等差数列求和
得出T(n) = (n^2+n)/2
属于平方阶O(n^2)
我们可以尝试通过减少内层循环的次数，来降低时间复杂度
-
那么关键点就是，如何减少内层循环次数
分析，我从外层拿到第 i 个数后：
如果它加上数组中的最大值还比目标数小
或者加上数组中的最小值还比目标值大
都说明数组中不可能存在一个数与当前数的和等于目标值
-
那么我只要通过一次循环查找一次最大和最小值就可以完成
上代码
/**
* 通过判断边界值，减少暴力匹配的次数
*/
public static int[] twoSum1(int[] nums, int target) {
//先找出nums中的最大值最小值
int max = nums[0];
int min = nums[0];
for (int num : nums) {
if (num >= max) {
max = num;
}
if (num < min) {
min = num;
}
}
//如果最大值加最大值都小于target，并且最小值加最小值都大于target，直接返回null
if (max+max < target && min+min>target){
return null;
}
//开始遍历
for(int i = 0;i<nums.length-1;i++){
//获得当前数和最大值、最小值的和
int iMax = nums[i] + max;
int iMin = nums[i] + min;
//如果当前遍历的数加上最大值都比target小，或者加上最小值都比target大，不用找了
if (iMax <target || iMin >target){
continue;
}
//否则再去向后找
for(int j=i+1;j<nums.length;j++){
if(nums[i]+nums[j]==target){
return new int[]{i,j};
}
}
}
return null;
}
时间复杂度分析：
这里的时间复杂度，具有不确定性，要看不用进行内层遍历的数量
最坏的情况是相比较原来，还多了一次寻找最值的循环
T(n) = (n^2+n)/2 + n
最好的情况是通过最值直接确定不可能有两数和等于目标
T(n) = n
那么多数情况都是介于两者之间，所以普适性的情况下来看，肯定还是提升了效率的
那么在LeetCode上执行一下看看效果吧
- 执行用时：1ms > 99.52%
- 内存消耗：41.3MB > 76.62%
当时非常出乎我的意料，提升非常大，还是蛮不错的
方案三、哈希表
哈希表是一种可以让查询非常快的数据结构，这里不多讲这个
直接使用java实现好的一个哈希表结构，HashMap
也很简单，就是先把数组挨个存进哈希表，然后遍历数组，去哈希表中查找有没有相加为目标值的存在
注意点：可能会找到下标相同的，也就是遍历自己的时候，在hash表中找到了自己，会返回两个相同的下标{i,i}，根据我们的题目解读，这种情况是不被允许的，要排除
public int[] twoSum(int[] nums, int target) {
// 建立k-v ，一一对应的哈希表
HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>(nums.length(),1);
//所有数据都存入hash表
for(int i = 0; i < nums.length; i++){
hash.put(nums[i],i);
}
//从hash表中查找是否有相加等于target的
for(int i = 0; i < nums.length; i++){
if(hash.containsKey(target-nums[i])){
int j = hash.get(target-nums[i]);
if(i!=j){
return new int[]{i,j};
}
}
}
return null;
}
这里如果有研究过hashMap或者对哈希表这个数据结构比较了解的人，可能会想到一个问题，hash冲突
我一开始就觉得如果出现相同数据，必然产生hash冲突，产生数据覆盖，是会出错的，但运行发现并没有问题，所以又重新捋了一遍，从HashMap的底层实现开始，最终确定确实是不会有问题，但这个过程还是很重要的
涉及到很多底层的东西，我简单讲一点点
HashMap中key是有讲究的，首先会用key调用他的hashCode()方法获取到一个hashCode，再用hashCode%一个数组长度（源码中是位运算），可以确定存放数据的数组索引位置，此时会让新put的数据尝试存入这个位置，要分情况讨论，如果这个位置是空的，非常简单，直接将数据封装到里边一个 静态内部类Node 中（它是一个链表）直接作为头结点，存在这里；如果这个位置已经有数据了（是一个实现了Entry的Node结点表示的链表），那么继续判断，和链表中每一个数据，先判断hash是否相同，再用equals方法比较key是否相同，如果找到任意一个相同，那么这个key对应的value会被覆盖，如果没有找到key相同的，就存在链表的最后边（这里先不谈树化为红黑树的事情）。
然后看一下Integer重写的hashCode方法，发现它是会返回自己本身
所以根据这个过程，会发现，确实发生了数据的覆盖，举个例子就是，如果存数组{3,3,3}，挨个给HashMap中put，put(3,0);put(3,1);put(3,2)，最后会发现只存了一个key为3，value为2的数据，get(3)会得到2。
这时候有同学就会问了，这不是有问题吗，这都覆盖了
从哈希冲突的角度来看，确实前面的两个数据丢失了，但只考虑计算解决两数之和这个问题，所有重复数据都只保留一个其实是正确的
为什么呢，因为最终虽然哈希表中只保存下来了一个，但数组中三个都在，所以其实没有丢，可以去带着这个思考看一看代码，debug一下nums = {3,3,3};target = 6这个案例，应该就明白了
在LeetCode中测试一下效率
- 执行用时：4ms > 53.964%
- 内存消耗：42.3MB > 70%左右吧，忘了记录了...
并没有很厉害，不如笔者自己的边界值排除
方案四、评论区发现一个对HashMap的巧妙使用
我简单优化了一下原来的代码，它原本创建hashmap对象是没有定义初始大小的。减少扩容，直接指定为(int) (数组长度 / 0.75 + 1)，就好了(涉及HashMap的扩容机制，这里不多谈)
这是一个非常简单的优化，就不多说了，直接看代码
class Solution {
public int[] twoSum(int[] nums, int target) {
// 建立k-v ，一一对应的哈希表
HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>(nums.length + nums.length >> 2 + 1);
for(int i = 0; i < nums.length; i++){
if(hash.containsKey(nums[i])){
return new int[]{i,hash.get(nums[i])};
}
// 将数据存入 key为补数 ，value为下标
hash.put(target-nums[i],i);
}
return null;
}
}
自古评论出大佬，这确实是很巧妙了，真的不是很容易想得到
分析一下：
- 巧妙就巧妙在这里了，没有必要一定是我找到了和我相加等于目标值的，也可以是我等着被和我相加为目标值的数据找到
- 所以，没有必要一开始就把所有的数据都存进去，可以每遍历一个存一个
- 查找的时候，就只查在我之前就存进去的，找得到就返回，找不到再把自己存进哈希表，让后面的人来找我
- 这样大多数情况可以不用把所有数据都存进hash表就已经找到了，肯定会快
我们LeetCode运行试试效率
- 执行用时：1ms > 99.52%
- 内存消耗：41.3MB > 76.62%
又出乎我意料了，和我的边界值判断完全一致......
方案五、双向遍历
然后我去看了一下LeetCode上边，最快的示例代码
发现就只是搞了个双向遍历，然后一下子快的飞起，0ms，打败百分百，我有点不能接受
先贴一下代码吧
就是一个内外双层的双 双向遍历，没什么好解释的，直接看吧
public int[] twoSum(int[] nums, int target) {
for (int i=0,j=nums.length-1;i<j;i++,j--){
if (nums[i]+nums[j]==target){
return new int[]{i,j};
}
for (int k=i+1, n=j-1;k<=n;k++,n--){
if (target-nums[i]==nums[k]){
return new int[]{i,k};
}
if (target-nums[i]==nums[n]){
return new int[]{i,n};
}
if (target-nums[j]==nums[k]){
return new int[]{k,j};
}
if (target-nums[j]==nums[n]){
return new int[]{n,j};
}
}
}
return null;
}
时间效率飞起
- 执行用时：0ms > 100%
- 内存消耗：41.7MB > 32.77%
方案六、边界判断和其他方案融合
此时我突然发现，双向遍历和单向遍历，和我的边界值判断丝毫没有冲突
那可不可以融合起来呢，理论上应该是强强联合，飞起中的飞起呀！
试一下，直接上代码了
/**
* 通过判断边界值，减少暴力匹配的次数
* 再加上双向遍历
*
* 提交结果
* 执行用时：0ms > 100%
* 内存消耗：41.2MB > 91.79%
*/
public static int[] twoSum4(int[] nums, int target) {
//先找出nums中的最大值最小值
int max = nums[0];
int min = nums[0];
for (int num : nums) {
if (num >= max) {
max = num;
}
if (num < min) {
min = num;
}
}
//如果最大值加最大值都小于target，并且最小值加最小值都大于target，直接返回null
if (max+max < target && min+min>target){
return null;
}
//开始遍历
for (int i = 0, j = nums.length - 1; i < j; i++, j--) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
//获得当前数和最大值、最小值的和
int iMax = nums[i] + max;
int iMin = nums[i] + min;
int jMax = nums[j] + max;
int jMin = nums[j] + min;
//下标i对应的数据是否可以排除了
boolean iBoo = iMax < target || iMin > target;
//下标j对应的数据是否可以排除了
boolean jBoo = jMax <target || jMin >target;
//如果两个都排除
if (iBoo && jBoo){
continue;
}
//两个都不能排除
if (!iBoo && !jBoo){
for (int k = i + 1, n = j - 1; k <= n; k++, n--) {
if (target - nums[i] == nums[k]) {
return new int[]{i, k};
}
if (target - nums[i] == nums[n]) {
return new int[]{i, n};
}
if (target - nums[j] == nums[k]) {
return new int[]{k, j};
}
if (target - nums[j] == nums[n]) {
return new int[]{n, j};
}
}
continue;
}
//只排除i
if (iBoo){
for (int k = i + 1, n = j - 1; k <= n; k++, n--) {
if (target - nums[j] == nums[k]) {
return new int[]{k, j};
}
if (target - nums[j] == nums[n]) {
return new int[]{n, j};
}
}
continue;
}
//只排除j
for (int k = i + 1, n = j - 1; k <= n; k++, n--) {
if (target - nums[i] == nums[k]) {
return new int[]{i, k};
}
if (target - nums[i] == nums[n]) {
return new int[]{i, n};
}
}
}
return null;
}
这里就不多讲了，就是我的边界值判断和双向遍历融合了一下
测试果然是起飞的，时间上看不出来，可能需要更大量的测试用例才能体现差距了，但空间上确实看到了一些优势！
总结
至此第一题就解析完毕了，有没有学到点东西~
评论
暂无评论，抢个沙发？