从零破局：LeetCode 1 & 2 超详细解剖 - 算法思维的第一块敲门砖_leetcode怎么解题
前言：
“各位老铁，好久不见。是的，博客又双叒叕长草了。这次停更的理由，简单到令人发指：纯粹是因为懒。不是没想法，不是没选题，就是单纯的……不想动。那种下班后只想‘葛优躺’、周末只想‘游戏宅’的状态，懂的都懂。每次打开编辑器，感觉手指头有千斤重。
但心里总有个声音在嘀咕：再懒下去，脑子怕是要生锈得更快了。是时候重启一下了！思来想去，决定回归最基础、也最经典的起点——LeetCode上的‘两数之和’（第1题）和‘两数相加’（第2题）。别小看这两道题，它们就像算法世界的‘Hello World’，看似简单，却是理解哈希、链表、模拟等核心思想的绝佳入口。今天就让我们从这‘最初的记忆’开始，一起重新找回敲代码的节奏和乐趣吧！”
1.两数之和
1.1.题目来源
本题文章开头就说了，来自力扣，下面给出链接：1. 两数之和 - 力扣（LeetCode）
1.2.题目解读
本题可能各位读者一上来就认为这个题目是很简单的，小编刚开始也是认为这个题目是很简单的，不过仔细做做就能发现这个题目是有点东西的。
题目上来给我们一个数组和一个目标值，它想让我们在这个数组中找到两个数，它们两个相加起来等于目标值，找到后返回他们的下标即可。题目还告诉我们：这个数组有且只有两个数加起来等于目标值，而不是许多个值。这其实无形中帮我们减轻难度了，下面我们看一眼例子，就可以大致了解本题的大概了。
下面我们根据对本题目的理解，开始进入本题的思路讲解环节了。
1.3.思路讲解
1.暴力穷举法
相信不少读者和我一样，看到这个题目，就会想到一个粗暴的方法：两个for循环直接把这个题目秒了。不得不说，这个方法确实是对的，并且难度系数也是最小的，相信第一次接触算法的读者可能会用到这个方法，这样做对初学者来说是很好的，但是对于我们这种学了很久的人来说，这种方法其实是很伤的，因为如果我们找寻的两个数，第一个数位于第一个位置，第二个数位于最后一个位置，那么这个时候我们的时间复杂度就来到了比较差的O(N^2)，所以小编不推荐这种做法，当然，等会的代码部分小编也是会讲这个方法的，因为不少读者我相信还是有小白的。
2.哈希表法（注：如果您还没学到哈希表，就可以把这个方法略过~）
虽然小编目前的博客进度还没有到哈希表，但是我不得不说，哈希表法可以说是最优秀的解法了，下面我来告诉各位它为什么可以是最佳解法。
这道题的核心任务是：给定一个数组和一个目标值，找到数组中两个不同的元素，使它们的和等于目标值。换句话说，对于数组中的每一个元素 num，我们都需要快速判断它的“另一半”——即目标值减去 num 得到的那个数（我们称为补数）——是否也存在于数组中，并且要知道它的具体位置（下标）。哈希表提供了解决查找效率低下的完美方案。其核心思路是：在遍历数组的过程中，一边走一边把已经见过的元素及其位置记录下来（存入哈希表），这样在后续检查任何一个元素时，都能瞬间知道它的补数是否出现过以及在哪里。这也是哈希表的特性，每当我们遍历一个数的时候，我们就可以把它放入哈希表中，在我们每次循环的时候，就可以在开头判断一下，哈希表之中，是否还存在着一个数：它就是目标值减去当前的数组中的值，如果存在的话，那么就可以说明我们找到了我们想要寻找的数，因为哈希表中存在的数是数组中的值，它表明之前数组中有个值，加上当前数组的值，就是目标值，所以我们直接返回当前的下标以及之前值的second即可。
对了，此时哈希表的时间复杂度其实是O(N)，因为它仅仅使用一个循环就可以找到两个值。
多说无益，下面我们进入代码讲解环节。
1.4.代码讲解
1.暴力穷举法
首先我们先说一下暴力穷举法，此时我们仅需先定义个for循环，这个for循环是从数组的开头就开始进行查询，当数组最后一个位置结束，这里的数代表我们要循环的第一个数。
vector twoSum(vector& nums, int target) { for(int i = 0 ; i < nums.size() ; i++) { } return {};}之后我们在来一个for循环，这个循环第一个放的值是i + 1，因为题目规定，不能使用相同位置的数相加，此时第二个条件依旧和第一个条件保持一致即可，之后也让它往后走。
for(int j = i + 1 ; j < nums.size() ; j++) //这个和上面的循环嵌套{}之后我们通过if语句进行条件的判断即可，此时我们需要判断两个位置的数相加是否为目标值即可，如果是的话，直接通过{}，里面放入下标i和j即可，至于为什么返回{}就行，它牵扯到了C++11新增的列表初始化，你只需要记住，它里面包含了一层隐式类型转换，它其实通过{}构造出了一个vector的临时对象，把临时对象返回了即可。当然，这并不是目前我们需要关注的问题，它涉及到语言方面的知识，到时候看小编出的C++文章即可。
if(nums[i] + nums[j] == target){ return {i,j};}如果没有存在两个数的和就是目标值，那么我们返回一个{}即可。
这就是穷举法的代码书写，是不是很easy呢？下面我们进行哈希表代码的书写。
2.哈希表法
此时，我们首先需要定义一个unordered_map类型的对象，它的底层是通过链式哈希表实现的，具体的实现过程请看我以后出的文章。它就是用来存储数组下标以及下标对应的值的。
unordered_map hash;此时我们就要进入一层循环了，这个循环其实和上面暴力穷举第一个循环的代码是一样的。
for(int i = 0 ; i < nums.size() ; i++){} //下面都是往里面填充的内容之后我们需要先进行一个判断，判断此时我们循环到的值它的补值是否在哈希表之中，此时我们需要借助哈希表的一个接口：find函数，它的作用就是查找我们所要查询的值是否在哈希表中，如果在的话，就返回当前位置的迭代器，我们通过迭代器就可以当前的i以及迭代器对应的second；如果不在，就可以把这个数组中的数存入哈希表之中。经过循环之后，我们就可以找到两个数。
auto it = hash.find(target-nums[i]);if(it != hash.end()){ return {it->second,i};}hash[nums[i]] = i;如果没有存在两个数的和就是目标值，那么我们返回一个{}即可。
1.5.完整代码
1.暴力穷举法
class Solution {public:vector twoSum(vector& nums, int target) { for(int i = 0 ; i < nums.size() ; i++) { for(int j = i + 1 ; j < nums.size() ; j++) { if(nums[i] + nums[j] == target) { return {i,j}; } } } return {};}};2.哈希表法
class Solution {public: vector twoSum(vector& nums, int target) { unordered_map hash; for(int i = 0 ; i second,i}; } hash[nums[i]] = i; } return {}; }};2.两数相加
2.1.题目来源
本题同样来自力扣：2. 两数相加 - 力扣（LeetCode）
2.2.题目解读
本题的理解需要和例子结合起来理解，通过上图以及题目我们就可以知道哦，本题目会给我们两个链表，这两个链表，我们需要反着把两个链表对应的数加起来，就看上面的例子，【2,4,3】和【5,6,4】，我们其实要算的是：
-
个位：2 + 5 = 7 (进位 0)
-
十位：4 + 6 = 10 -> 0 (进位 1)
-
百位：3 + 4 + 进位1 = 8 (进位 0)
-
输出：
7 -> 0 -> 8(代表 807) -
验证： 342 + 465 = 807
可能很多读者朋友都倒在了理解题目的过程中，这个题目其实简单来说就是让两个链表的值（反着读）相加起来，此时加起来的值我们在反过来，让每一位的值变为链表每个结点即可，下面我们就进行本题的思路讲解。
2.3.思路讲解
1.我自己的抽象做法
可能很多读者看到这个题目会懵，说实在的，我已经很久没有写算法题了，前几日突然认为这样不可取，于是开始进行了力扣的刷题之路，这个题目我刚开始想的做法最优解法其实有很大的出入，下面我简单的说一下我的解法：
当时我认为，我需要写一个接口，它负责计算链表的长度（今日我认为这个接口的实现很蠢），之后通过得到的链表长度，我在计算出链表反向后（这里的反向其实就是把第一个数当个位，以此类推）的数值大小，这里就用到前面的链表长度，因为它可以帮助我知道这个链表得出的数的最高位是几位，之后就可以算出大小了，分别算出两个链表的大小以后，之后我们就可以把两个链表得出的值加起来；之后，我写了一个接口让相加后的数反过来，反过来以后我又写了一个接口...，这个接口实现了把一个数在拆回链表的能力，之后返回新建链表的头结点，这就完成了本题目。
看着我的方法有点凌乱，其实一点也不整洁，当时真的，写算法题就想着硬解，当时我还碰到一个bug：我新建立的链表会多出来一个空的节点，此时我的方法就是：在遍历一遍节点，把最后一个节点省略掉，这样就能完成一个链表，当然，我这个方法确实通过了样例，当我兴致勃勃的去提交的时候，结果出来下面的结果：
主打的就是一个绝望，最后出问题的原因是：我在计算大小的时候，大概是因为链表太长了，导致存入的数超过了long long的大小，所以这个做法不可取，各位就当看乐子了。
2.逐位相加法
这个方法是本题最优的解法，下面我来简单介绍一下这个方法：
此时我们需要精确定义两个指针：第一个指针作为新链表的守护者，在首次开辟内存空间后立即将头节点的重任交付于它，确保根基稳固永不丢失；第二个指针则化身勤恳的编织者，接过构建链条的使命，代替头指针完成后续节点的衔接与延伸。当这对指针各司其职后，循环遍历的舞台便正式开启——由于两条输入链表的长度可能参差，我们在每次获取节点值时需借助简洁的三目表达式进行智慧裁决：若当前链表探针已触及尽头，则从容补零，确保加法运算不受干扰。然而数值的简单叠加并非终点，进位才是隐藏的挑战者！我们必须引入一个忠诚的进位变量，时刻铭记：当相加之和突破十的边界，个位数字将荣登当前节点宝座，而那溢出的十位荣光则化作进位的火炬，传递至高位的下一次运算。如此设计，逻辑清晰严密，堪称优雅。
以上就是逐位相加法，下面我们进行代码的实现。
2.4.代码讲解
1.我自己的抽象做法
这个我就不讲了，各位当做乐子看就行。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */class Solution {public: long long Getvalue(ListNode* l1,int x) { // int value = 1; long long i = 0; long long value1 = 0; while(l1 && x != 0) { long long a = pow(10,i); value1 += l1->val * a; l1 = l1->next; x--; i++; } long long h = value1; return h; } long long GetSize(ListNode* n1) { long long n = 0; while(n1 != nullptr) { n++; n1 = n1->next; } return n; } ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* n1 = l1; ListNode* n2 = l2; long long n = GetSize(n1),m = GetSize(n2); long long m1 = Getvalue(l1,n); long long x2 = Getvalue(l2,m); long long longth = m1 + x2; ListNode* ll1 = new ListNode(longth % 10); ll1->next = new ListNode; ListNode* x1 = ll1 ->next; longth = longth / 10; while(longth) { long long h1 = longth % 10; x1 ->val = h1; x1 -> next = new ListNode; x1 = x1->next; longth /= 10; } return ll1; }};2.逐位相加法
·首先，我们需要定义好两个链表以及一个表示进位的变量。
ListNode *head = nullptr, *tail = nullptr;int carry = 0;之后，我们就开始进行循环，循环的条件其实比较容易，我们需要让最长的链表循环完，但是判断一个最长的链表也是需要额外写一个函数的，所以我的建议就是通过或运算符，当两个链表都为空的时候，就代表了最长的链表循环完了。
while (l1 || l2){ //之后内容都在循环里面}首先我们需要分别把链表里面的值提取出来，此时我们需要通过三目表达式进行判断链表是不是为空的，如果是空的话，那么就直接让改值为0即可，不影响结果，之后我们在定义一个变量用来保存两个数相加的结果，不过此时我们也需要把进位加上，如果前面的数相加大于10的话，后面的数就需要加一位，当然，如果没有进位的话，因为是0，所以不影响结果。
int n1 = l1 ? l1->val: 0;int n2 = l2 ? l2->val: 0;int sum = n1 + n2 + carry;之后我们就开始进行条件的判断了，如果头结点为空的话，那么直接把新开辟的节点当做头节点，如果头结点存在的话，那么直接插入到tail中即可，插入完以后就往后走，之后我们在进行进位的判断，其实判断的逻辑还是很容易的，此时仅需让sum/10，得到的就是进位后的值，无非就是0或者是1,1代表进位了，0代表没有进位。然后一切工作做完以后，我们直接让两个链表各自往后走，不过记得判断链表是否为空哦~
if (!head) { head = tail = new ListNode(sum % 10);} else { tail->next = new ListNode(sum % 10); tail = tail->next;}carry = sum / 10; if (l1) { l1 = l1->next;}if (l2) { l2 = l2->next;}最后循环结束我们返回头结点即可。
2.5.完整代码
class Solution {public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode *head = nullptr, *tail = nullptr; int carry = 0; while (l1 || l2) { int n1 = l1 ? l1->val: 0; int n2 = l2 ? l2->val: 0; int sum = n1 + n2 + carry; if (!head) { head = tail = new ListNode(sum % 10); } else { tail->next = new ListNode(sum % 10); tail = tail->next; } carry = sum / 10; if (l1) { l1 = l1->next; } if (l2) { l2 = l2->next; } } if (carry > 0) { tail->next = new ListNode(carry); } return head; }};3.小结
我是忘梓，现在是2025年5月的最后一天，凌晨1点14，我终于把这篇博客写完了....这是本周的第一篇博客，话说为什么今天才发布博客，我前面有所讲解——因为我懒。我自责，我忏悔，我下次一定按时写博客（应该吧）。本文到这里也就结束了，如果各位还有什么不懂的，可以加文末小编的微信，小编会解决各位的疑惑。
