题目 1. 两数之和

【哈希表】变形：nums[j] = tarhet - nums[i]，一边枚举j，一边把nums[j]和j加到哈希表中。

(资料图片)

题目 2. 两数相加

【递归】每次把两个节点值，和进位值carry相加，除以10的余数即为当前节点需要保存的数位，除以10的商即为新的进位值。技巧：如果发现l2比l1场可以交换l1和l2，保证l1不是空节点从而简化代码逻辑。

【迭代】初始化答案为一个空链表，每次循环向该链表末尾添加一个节点，循环即遍历链表l1和l2，每次把两个节点值，与进位值carry相加，除以10的玉树即为当前节点需要保存的数位，除以10的上即为新的进位制。在第一次循环时无法往一个空节点末尾添加节点，所以要创建一个哨兵节点当成初始的空链表，循环结束后哨兵节点下一个节点就是要返回的链表头节点。

题目 445. 两数相加 II

【递归】反转链表l1和l2，调用两数相加的代码，得到链表l3，最后返回反转后的l3。

【迭代】

题目 2679. 矩阵中的和

【排序】对每行排序，转置后，遍历每一列，找到每一列的最大值并相加。

题目 2600. K 件物品的最大和

【贪心】按照1,0,-1的顺序选，先选1，如果k≤numOnes那么答案就是k。再选0，如果k≤numOnes+numZeros那么答案为numOnes。最后选-1（题目要求恰好选k个），那么剩余必须选k-numOnes-numZeros个一1，答案为numOnes+(k-numOnes-numZeros).(-1)=+numZeros-k。

题目 2178. 拆分成最多数目的正偶数之和

【贪心】finalSum分解成偶数之和，而偶数+偶数=偶数，所以finalSum必须是偶数，既然要尽可能多的分解且分解出的偶数各不相同，可以按照2468的顺序分解，减小finalSum，直到finalSum小于要分解出的数为止，最后把剩余的finalSum加到最后一个分解出的偶数上。

题目 2532. 过桥的时间

【模拟】建立4个堆，每个堆都记录工人下标和完成时间（到达桥的时间），这4个堆从左到右分别表示：workL：新仓库正在放箱的工人；waitL：左边等待过桥的工人；waitR：右边等待过桥的工人；workR；旧仓库正在搬箱的工人。记录当前时间cur，不断循环直到所有箱子被搬完，每次循环： ①把完成时间不超过cur的workL弹出，放入waitL中；②把完成时间不超过cur的vorkR弹出，放入waitR中；③如果watR不为空，出堆，过桥，更新cur为过完桥的时间，然后把这个工人放入workL中（记录完成时间）；④否则如果watL不为空，出堆，过桥，更新c2ur为过完桥的时间，然后把这个工人放入workR中（记录完成时间），同时把n减一；⑤否则说明cur过小，找个最小的放箱/搬箱完成时间来更新cur。循环结束后，不断弹出wokR，过桥，最后一个工人过完桥的时间即为答案。

题目 167. 两数之和 II - 输入有序数组

【双指针】定义两个指针i和j，分别指向数组的第一个和最后一个元素，每次计算nums[i]+nums[j]如果等于target就返回[i+1,j+1]即可，如果和小于目标值，将i右移一位，如果和大于目标值，将j左移一位。

题目 15. 三数之和

【排序 + 双指针】不用按照顺序返回三元组，所以可以对数组进行排序，能跳过重复元素，枚举三元组第一个元素nums[i]，对于每个i，维护两个指针j=i+1和k=n-1，找到满足nums[i] + nums[j] + nums[k] = 0的j和k，在枚举的过程中，需要跳过重复的元素，避免出现重复的三元组。具体判断逻辑如下：如果i>0且nums[i]=nums[i-1]说明枚举的元素与上一个元素相同直接跳过，如果nums[i]>0，说明当前枚举的元素>0，三数之和必然无法等于0，结束枚举。否则令左指针J=i+1，右指针k = n -1，当j0，说明nums[k]太大，需要将k左移一位。否则，说明我们找到一个合法的三元组，将其加入答案并将j右移一位，k左移一位，同时跳过所有重复的元素，继续寻找下一个合法的三元组。

题目 16. 最接近的三数之和

【双指针】排序后枚举nums[i]作为第一个数，找另外两个数使得三个数和与target最接近。设s为三数之和，mindiff维护|s-target|的最小值。如果s=target，那么答案就是s，直接返回s；如果s>target，那么如果s-target<min Diff，说明找到了一个与target更近的数，更新minDiff为s-target，更新答案为s。然后和三数之和一样，把k减一；否则s<target，那么如果target-s<min Diff，说明找到了一个与target更近的数，更新minDiff为target-s，更新答案为s。然后和三数之和一样，把j加一。

题目 1911. 最大子序列交替和

【DP】定义f[i]为从前i个元素中选出的子序列，且最后一个元素为奇数下标时的最大交替和，g[i]为从前i个元素中选出的子序列，且最后一个元素为偶数下标时的最大交替和，初始f[0] = g[0] = 0，答案为max(f[n], g[n])。考虑第i个元素nums[i-1]，如果选取该元素为奇数下标，上一个元素必须为偶数下标，只能从前i-1个元素中选取，因此f[i] = g[i-1]- nums[i -1]，如果不选取，f[i] = f[i- 1]。如果选取该元素并且该元素为偶数下标，那么上一个元素必须为奇数下标，只能从前i-1元素选取，因此g[i] = f[i-1]+nums[i-1]，不选取该元素那么g[i] = g[i-1]，状态转移方程f[i] = max(g[i - 1] - nums[i -1], f[i - 1])，g[i] = max(f[i - 1] - nums[i -1], g[i - 1])。最终答案为max(f[n], g[n])。

题目 2544. 交替数字和

【模拟】从最低位开始，通过n mod 10得到个位数，再把n除以10，重复前面过程，得到十位数、百位数，最后得到最高位，如果它取负号则把答案取反。

题目 931. 下降路径最小和

【DP】定义f[r] [c]为从matrix[r] [c]出发向上走到第一排的路径最小和，f[r] [c] = min(f[r - 1] [c - 1], f[r- 1] [c], f[r- 1] [c + 1]) + matrix[r] [c]。修改边界+类似01背包空间优化→f[c + 1] = min(f[c], f[c+1], f[c+2]) + matrix[r] [c]。

题目 979. 在二叉树中分配硬币

【DFS】定义d = coins - nodes，计数器的值就是|d|，d = d_left + d_right + - 1。

题目 18. 四数之和

【排序 + 双指针】设s = nums[a] + nums[a + 1] + nums[a + 2] + nums[a + 3]，如果s > target，由于数组已经排序，后面无论怎么选，选出四个数的和不会比s还小，后面不会找到等于target的四数之和了，只要s>target，break；设s = nums[a] + nums[n - 3] + nums[n - 2] + nums[n - 1]。如果s0且nums[a] = nums[a - 1]，那么nums[a]和后面数字相加的结果，必然在之前算出过，所以无需执行后续代码，直接continue外才能循环。对于nums[b]的枚举，也有类似优化：设s = nums[a] + nums[b] + nums[b - 1] + nums[b + 2]。如果s >target，由于数组已经排序，选出的四个数的和不会比s还小，后面不会找到等于target的四叔之和了，所以s>target，直接break。设s = nums[a] + nums[b] + nums[n - 1]+ nums[n -1 ]，如果sa+1且nums[b] = nums[b - 1]那么nums[b]和后面数字相加的结果，必然在之前算出过，所以无需执行后续代码，直接contitnue，注意这里b>a+1的判断是必须的，如果不判断，示例2这样的数据会直接continue。

题目 834. 树中距离之和

【换根DP】从0出发DFS，累加0到每个点的距离，得到ans[0]。DFS的同时，计算出每棵子树的大小size[i]。然后从0出发再次DFS，设y是x的儿子，那么：ans[y] = ans[x] + [y]。利用该公式可以自顶向下递推得到每个αns[i]。

题目 415. 字符串相加

【双指针】我们用两个指针i和j分别指向两个字符串的末尾，从末尾开始逐位相加。每次取出对应位的数字a和b，计算它们的和a+b+c，其中c表示上一次相加的进位，最后将a+b+c的个位数添加到追加到答案字符串的末尾，然后将α+b+c的十位数作为进位c的值，循环此过程直至两个字符串的指针都已经指向了字符串的开头并且进位c的值为0。最后将答案字符串反转并返回即可。

题目 1851. 包含每个查询的最小区间

【排序 + 离线查询 + 优先队列（小根堆）】注意到查询的顺序不会影响答案，并且涉及到的区间也不会发生变化，因此考虑将所有查询按照从小到大的顺序排序，同时将所有区间按照左断电从小到大的顺序进行排序。用一个优先队列pq维护当前所有的区间，队列每个元素是一个二元组(v,r)，表示区间长度为v，右端点为r的区间。初始时，优先队列为空，另外定义一个指针i指向当前遍历到的区间，初始时i=0，按照从小到大的顺序一次遍历每个查询(i,j)，并进行如下操作：如果指针i尚未遍历完所有区间，并且当前遍历到的区间[a,b]的左端点小于等于x，那么将该区间加入优先队列中，并将指针i后裔一位，循环此过程；如果优先队列不为空，且对顶元素区间右端点小于x，将对顶元素弹出，循环此过程；如果优先队列不为空，对顶元素就是包含x的最小区间，将其长度v加入答案数组ans中。

题目 874. 模拟行走机器人

【哈希表 + 模拟】定义一个长度为5的方向数组dirs=[0,1,0,-1,0]，数组中2个相邻元素表示一个方向，即(dirs[0], dirs[1])表示向北，而(dirs[1], dirs[2])表示向东。用哈希表s存所有障碍物的下标，另外用两个变量x和y表示机器人当前所在坐标，k表示机器人当前的方向，答案变量ans表示机器人距离远点的最大欧式距离的平方，接下来遍历commands的每个元素c，c=-1则左转90°即k = (k + 3) mod 4；c= -1表示机器人向右转90°，k = (k + 1) mod 4; 否则向前移动c个单位长度。

题目 918. 环形子数组的最大和

【DP】计算最大非空子数组和macS以及最小子数组和mimS。（注意最小子数组可以是空的，但不能是整个数组。）如果mimS=sum（nums），返▣macS，否则返▣max{macS，sum（nums）-mimS}。

题目 1499. 满足不等式的最大值

【单调队列】yi+yj=|xi-xj| = yi+yj+xj-xi = (xi+yj) + (yi-xi)，枚举j，问题变成计算yi-xi的最大值，其中i<j且xi>xj-k。用单调队列优化：单调队列存储二元组(xi,yi-xi)，首先把队首的超出范围的数据出队，即xi<xj-k的数据，然后把(xj,yj-xj)入队，入队前如果发现yj-xj不低于队尾的数据，直接弹出队尾，这样维护后，单调队列的yi-xi从队首到队尾是严格递减的，yi-xi的最大值即为队首的最大值。

题目 860. 柠檬水找零

【分类讨论】5美元能用于10美元和20美元的诏令，所以5比10更通用，所以优先用10，用完了再用5。设当前有five张5美元钞票，ten张10美元钞票。设b=bills[i]分类讨论。

题目 42. 接雨水

【DP】定义left[i]表示下标i位置及其左边的最高柱子的高度，定义right[i]表示下标i位置及其右边最高柱子的高度，下标i位置能接的雨水量是min(left[i], right[i]) - height[i]，遍历数组，计算出Left[i]和right[i]，最后答案为Σmin(left[i], right[i]) - height[i]。

题目 771. 宝石与石头

【数组】用一个数组s记录所有宝石的类型，遍历所有石头统计答案。

题目 2208. 将数组和减半的最少操作次数

【优先队列（大根堆）】每次取数组当前最大值进行减半，减半后的数重新放回大根堆里。

题目 2569. 更新数组后处理求和查询

【Lazy 线段树】假设nums1中总共有c个1，那么操作2相当于把nums2的元素和增加了c·p。所以只需要维护nums1中1的个数。如何实现操作1？用Lazy线段树维护区间内1的个数cnt，以及整个区间是否需要反转的Lazy标记p。

题目 2500. 删除每行中的最大值

【排序】每一次操作是从每一行删除最大值，然后取最大值加到答案中，因此可以先对每一行进行排序，接下来遍历每一列取每一列的最大值，然后加到答案中。

题目 2050. 并行课程 III

【拓扑排序 + DP】定义f[i]为完成第i门课需要花费的最少月份数，根据题意，只有当i的所有先修课都完成时，才能开始学习第i门课，并且可以立即开始，所以f[i] = time[i] + max(f[j])，j是i的先修课。由于题目保证图是一个有向无环图，所以一定存在拓扑序，可以在计算拓扑序的同时计算状态转移。设当前节点为x，可以在计算出f[x]后，更新y的所有秀安修课耗时的最大值，x是y的先修课，答案是所有f[i]的最大值。

题目 141. 环形链表

【快慢指针】定义快慢指针fast和slow，初始时均指向head，快指针每次走两步，慢指针每次走一步，不断循环，当快慢指针相遇时说明链表存在环。

题目 142. 环形链表 II

【快慢指针】先用快慢指针判断链表是否有环，如果有环，再定义一个答案指针ans指向链表头部，让ans和慢指针一起走，每次走一步，直到ans和慢指针相遇，相遇的节点为环的入口节点。

题目 143. 重排链表

【快慢指针 + 反转链表 + 合并链表】先用快慢指针找到链表的中点，然后将链表后半部分反转，最后将左右两个链表合并。