001.两数之和

作者：沉默王二发布时间：2023-12-09T10:03:59.521+0800

之前星球还没有 Markdown 的功能，所以第一次发布的格式在星球里阅读的话很不友好，于是二哥打算重新优化一版《二哥的 LeetCode 刷题笔记》：

增加代码注释，这样大家更容易看懂并掌握题解；
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
增加手绘图，这样大家更容易理解解题思路；
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

并且增加了技术派专栏的阅读地址，只需要绑定星球编号就可以通过「微信扫码登录」的方式在技术派网站上阅读，这样大家的阅读选择也会更加多样化（语雀、技术派、星球都可以，喜欢哪个用哪个）。

语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
技术派专栏地址：https://paicoding.com/column/7/1
星球原地址：https://t.zsxq.com/159tj8OLT

我知道，市面上已经有不少的刷题笔记了，二哥也看过很多，但讲真，有些还是看不太懂，可能是因为天赋不够，也可能是因为这些刷题笔记一开始是针对 C语言、Python、Go 或者 C++ 的，后来才翻译成 Java 语言，就导致阅读起来并不幸福🥰。

那我希望《二哥的 LeetCode 刷题笔记》能够给学习算法的球友提供一些不一样的刷题思路，从我自己的角度出发，题解可能会更容易掌握，当然了，最重要的还是教给大家举一反三的解题能力。

这对于那些打算冲中大厂的球友来说，至关重要，因为中大厂几乎都会有算法的笔试题，然后才会有面试机会。当然了，对于那些想通过刷题来学习 Java 的球友，无疑也会多一种选择，冲。

在这里，必须要感谢球友 @炳源，是我们的通力配合，才有了球友们看到的这份市面上独一无二的 LeetCode 刷题笔记。好，就让我们开始吧！

001.两数之和

题意

给出一个数组和一个目标值，让你在数组中找出和为目标值的两个数，并且这两个数在数组中的下标（索引）不同。

示例

输入：nums=[2,7,11,15],target=9

解释：因为nums[0]+nums[1]==9，返回[0,1]

难度

简单

分析

我相信，大部分**球友 **都能想到暴力破解，即便你是算法小白，以前从来没有刷过 LeetCode。

当然了，没有一点 Java 基础肯定是不行的，所以推荐你先去看看**二哥的 Java 进阶之路 **，最起码刷一个星期把语法先掌握了。

好，所谓的“暴力”，在算法领域表示“穷举、极低效率的实现”。主要源于这个英文单词（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("没有找到");    }

}

笔试如果遇到不太会的题，就暴力。不过两次遍历的时间复杂度是。

时间复杂度，在算法领域是一个非常重要的概念，一个衡量算法执行时间随输入数据规模增长而增长的度量。在这个特定的 “两数之和” 问题的解法中，时间复杂度是由两层嵌套循环决定。

我在二哥的 Java 进阶之路里有详细地解释过，**戳链接 **了解。

的时间复杂度实在是太不理想，效率太低，在所有 Java 提交中只能击败不到 28% 的用户。

能不能优化一下呢？

观察第二个循环，我们是从每个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("没找到");    }}

虽然击败了 33% 的 Java 选手，但是这样的算法时间复杂度和之前相比根本没有变化。

我们反推一下。

已知 i 和 target，那么target - i就是与 i 相配对的另一个数，我们只需要判断target - i是否在 i 之前出现过，如果出现过，那么这两个数就是我们要找的数。

那么问题来了，如何判断target - i是否在 i 之前出现过呢？

我们可以用一个 HashMap 来记录数组中的每一个元素，元素的索引作为哈希表的 key，元素本身作为 value，当发现target - i在哈希表中存在时，就可以直接返回这两个数的索引了。来看题解。

class Solution {

public int[] twoSum(int[] nums, int target) {        // 创建一个哈希表来存储数组元素和它们的索引        Map<Integer, Integer> map = new HashMap<>();        // 遍历数组中的每个元素        for(int i = 0; i < nums.length; i++){            // 计算与当前元素相配对的另一个元素的值            int complement = target - nums[i];            // 检查哈希表中是否已存在这个配对元素            if(map.containsKey(complement))                // 如果存在，返回当前元素的索引和配对元素的索引                return new int[]{i, map.get(complement)};            // 将当前元素及其索引添加到哈希表中            map.put(nums[i], i);        }        // 如果遍历完数组都没有找到符合条件的两个数，则抛出异常        throw new IllegalArgumentException("没找到");    }}

当输入是 nums = [2,7,11,15] 和 target = 9 时，我们来模拟上述解决 “两数之和” 的整个过程：

初始化哈希表：开始时，哈希表为空。
遍历数组：
第一个元素（i = 0）：nums[0] = 2
计算 complement = target - nums[i] = 9 - 2 = 7。
检查哈希表中是否存在 7。目前哈希表为空，所以不存在。
将 (2, 0) 加入哈希表（值为 2，索引为 0）。
第二个元素（i = 1）：nums[1] = 7
计算 complement = 9 - 7 = 2。
检查哈希表中是否存在 2。是的，它存在，并且索引为 0。
找到匹配的一对元素：nums[0] = 2 和 nums[1] = 7，它们的和为 9。
返回这两个元素的索引 [1, 0]。

因此，对于输入 nums = [2,7,11,15] 和 target = 9，该题解会返回 [1, 0] 作为结果，表示 nums 数组中索引为 1 和 0 的元素相加得到目标值 9。

时间复杂度：

空间复杂度：

哦吼，这次结果就不一样了，打败了 71% 的选手，效果显著。

总结

对于本题，我们用到了 Java 中的一个普通 for 循环，和一个 HashMap，这两个都是 Java 中必须掌握的知识，如果你对这两个都不熟悉，那么你的 Java 基础还是不够扎实。

建议通过下面三个链接来学习：

力扣链接：https://leetcode.cn/problems/two-sum/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4000+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

之前星球还没有 Markdown 的功能，所以第一次发布的格式在星球里阅读的话很不友好，于是二哥打算重新优化一版《二哥的 LeetCode 刷题笔记》：

增加代码注释，这样大家更容易看懂并掌握题解；
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
增加手绘图，这样大家更容易理解解题思路；
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
技术派专栏地址：https://paicoding.com/column/7/1
星球原地址：https://t.zsxq.com/159tj8OLT

在这里，必须要感谢球友 @炳源，是我们的通力配合，才有了球友们看到的这份市面上独一无二的 LeetCode 刷题笔记。好，就让我们开始吧！

001.两数之和

题意

给出一个数组和一个目标值，让你在数组中找出和为目标值的两个数，并且这两个数在数组中的下标（索引）不同。

示例

输入：nums=[2,7,11,15],target=9

解释：因为nums[0]+nums[1]==9，返回[0,1]

难度

简单

分析

我相信，大部分**球友 **都能想到暴力破解，即便你是算法小白，以前从来没有刷过 LeetCode。

当然了，没有一点 Java 基础肯定是不行的，所以推荐你先去看看**二哥的 Java 进阶之路 **，最起码刷一个星期把语法先掌握了。

好，所谓的“暴力”，在算法领域表示“穷举、极低效率的实现”。主要源于这个英文单词（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("没有找到");    }

}

笔试如果遇到不太会的题，就暴力。不过两次遍历的时间复杂度是。

我在二哥的 Java 进阶之路里有详细地解释过，**戳链接 **了解。

的时间复杂度实在是太不理想，效率太低，在所有 Java 提交中只能击败不到 28% 的用户。

能不能优化一下呢？

观察第二个循环，我们是从每个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("没找到");    }}

虽然击败了 33% 的 Java 选手，但是这样的算法时间复杂度和之前相比根本没有变化。

我们反推一下。

那么问题来了，如何判断target - i是否在 i 之前出现过呢？

class Solution {

public int[] twoSum(int[] nums, int target) {        // 创建一个哈希表来存储数组元素和它们的索引        Map<Integer, Integer> map = new HashMap<>();        // 遍历数组中的每个元素        for(int i = 0; i < nums.length; i++){            // 计算与当前元素相配对的另一个元素的值            int complement = target - nums[i];            // 检查哈希表中是否已存在这个配对元素            if(map.containsKey(complement))                // 如果存在，返回当前元素的索引和配对元素的索引                return new int[]{i, map.get(complement)};            // 将当前元素及其索引添加到哈希表中            map.put(nums[i], i);        }        // 如果遍历完数组都没有找到符合条件的两个数，则抛出异常        throw new IllegalArgumentException("没找到");    }}

当输入是 nums = [2,7,11,15] 和 target = 9 时，我们来模拟上述解决 “两数之和” 的整个过程：

初始化哈希表：开始时，哈希表为空。
遍历数组：
第一个元素（i = 0）：nums[0] = 2
计算 complement = target - nums[i] = 9 - 2 = 7。
检查哈希表中是否存在 7。目前哈希表为空，所以不存在。
将 (2, 0) 加入哈希表（值为 2，索引为 0）。
第二个元素（i = 1）：nums[1] = 7
计算 complement = 9 - 7 = 2。
检查哈希表中是否存在 2。是的，它存在，并且索引为 0。
找到匹配的一对元素：nums[0] = 2 和 nums[1] = 7，它们的和为 9。
返回这两个元素的索引 [1, 0]。

因此，对于输入 nums = [2,7,11,15] 和 target = 9，该题解会返回 [1, 0] 作为结果，表示 nums 数组中索引为 1 和 0 的元素相加得到目标值 9。

时间复杂度：

空间复杂度：

哦吼，这次结果就不一样了，打败了 71% 的选手，效果显著。

总结

建议通过下面三个链接来学习：

力扣链接：https://leetcode.cn/problems/two-sum/

一步一个脚印

（优惠券仅 300 张，数量有限）

之前星球还没有 Markdown 的功能，所以第一次发布的格式在星球里阅读的话很不友好，于是二哥打算重新优化一版《二哥的 LeetCode 刷题笔记》：

增加代码注释，这样大家更容易看懂并掌握题解；
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
增加手绘图，这样大家更容易理解解题思路；
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
技术派专栏地址：https://paicoding.com/column/7/1
星球原地址：https://t.zsxq.com/159tj8OLT

在这里，必须要感谢球友 @炳源，是我们的通力配合，才有了球友们看到的这份市面上独一无二的 LeetCode 刷题笔记。好，就让我们开始吧！

001.两数之和

题意

给出一个数组和一个目标值，让你在数组中找出和为目标值的两个数，并且这两个数在数组中的下标（索引）不同。

示例

输入：nums=[2,7,11,15],target=9

解释：因为nums[0]+nums[1]==9，返回[0,1]

难度

简单

分析

我相信，大部分**球友 **都能想到暴力破解，即便你是算法小白，以前从来没有刷过 LeetCode。

当然了，没有一点 Java 基础肯定是不行的，所以推荐你先去看看**二哥的 Java 进阶之路 **，最起码刷一个星期把语法先掌握了。

好，所谓的“暴力”，在算法领域表示“穷举、极低效率的实现”。主要源于这个英文单词（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("没有找到");    }

}

笔试如果遇到不太会的题，就暴力。不过两次遍历的时间复杂度是。

我在二哥的 Java 进阶之路里有详细地解释过，**戳链接 **了解。

的时间复杂度实在是太不理想，效率太低，在所有 Java 提交中只能击败不到 28% 的用户。

能不能优化一下呢？

观察第二个循环，我们是从每个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("没找到");    }}

虽然击败了 33% 的 Java 选手，但是这样的算法时间复杂度和之前相比根本没有变化。

我们反推一下。

那么问题来了，如何判断target - i是否在 i 之前出现过呢？

class Solution {

public int[] twoSum(int[] nums, int target) {        // 创建一个哈希表来存储数组元素和它们的索引        Map<Integer, Integer> map = new HashMap<>();        // 遍历数组中的每个元素        for(int i = 0; i < nums.length; i++){            // 计算与当前元素相配对的另一个元素的值            int complement = target - nums[i];            // 检查哈希表中是否已存在这个配对元素            if(map.containsKey(complement))                // 如果存在，返回当前元素的索引和配对元素的索引                return new int[]{i, map.get(complement)};            // 将当前元素及其索引添加到哈希表中            map.put(nums[i], i);        }        // 如果遍历完数组都没有找到符合条件的两个数，则抛出异常        throw new IllegalArgumentException("没找到");    }}

当输入是 nums = [2,7,11,15] 和 target = 9 时，我们来模拟上述解决 “两数之和” 的整个过程：

初始化哈希表：开始时，哈希表为空。
遍历数组：
第一个元素（i = 0）：nums[0] = 2
计算 complement = target - nums[i] = 9 - 2 = 7。
检查哈希表中是否存在 7。目前哈希表为空，所以不存在。
将 (2, 0) 加入哈希表（值为 2，索引为 0）。
第二个元素（i = 1）：nums[1] = 7
计算 complement = 9 - 7 = 2。
检查哈希表中是否存在 2。是的，它存在，并且索引为 0。
找到匹配的一对元素：nums[0] = 2 和 nums[1] = 7，它们的和为 9。
返回这两个元素的索引 [1, 0]。

因此，对于输入 nums = [2,7,11,15] 和 target = 9，该题解会返回 [1, 0] 作为结果，表示 nums 数组中索引为 1 和 0 的元素相加得到目标值 9。

时间复杂度：

空间复杂度：

哦吼，这次结果就不一样了，打败了 71% 的选手，效果显著。

总结

建议通过下面三个链接来学习：

力扣链接：https://leetcode.cn/problems/two-sum/

一步一个脚印

（优惠券仅 300 张，数量有限）

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412