前言

从力扣100题开始的算法总结，决定真正走科班的代码之路后，果然还是得彻底从头开始总结一些算法代码了，感觉会是一个长期的总结过程，而且还要保持长期热情，只能加油吧。之前技能点全点在做游戏上了，但如果真的决定要改变世界，那就不能止步不前了。

这个总结目前来说还比较简单片面，后续可能考虑针对各个算法进行单一深入应用总结。

wallhaven-5g22q5_1920x1080

哈希

这一部分其实主要是利用哈希表来辅助解决问题。

可能困难比较大的是记住哈希表的使用方式（呃呃这就是记性差的坏处了）

记住之后很多问题在考虑到查找、拼接就可以直接从哈希表入手了：

unordered_map<string, vector<string>> groups;
for(auto it = groups.begin(); it != groups.end(); it++)
{
    ans.emplace_back(it->second);           // 每一组键值对的值加入结果中
}

unordered_set<int> st(nums.begin(), nums.end()); // 把 nums 转成哈希集合
st.contains(x - 1); // 哈希判断条件

经典题目链接：

49. 字母异位词分组 - 力扣（LeetCode）

128. 最长连续序列 - 力扣（LeetCode）

双指针

双指针题目比较灵活，可以有以下两类（目前）：

  1. 指针同时出发，主要挪动一个指针，满足特定条件再挪动另一个指针
  2. 指针同时出发，但是位于数列两端，进行比较选择挪动的指针

代表性题目分别有：

283. 移动零 - 力扣（LeetCode）

42. 接雨水 - 力扣（LeetCode）

滑动窗口

先附上比较玄妙的一道题：

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

这个的话比较字面意思，有点像双指针，主要通过动态调节窗口大小，来满足特定条件

主要操作是拓展窗口、缩减窗口、比较、选择。

然后可能会和子串在一起。

子串

这道题非常有意思：

76. 最小覆盖子串 - 力扣（LeetCode）

双指针两个指针负责不同事物

一个负责找全

一个负责缩小

原理上还是滑动窗口

普通数组

矩阵

48. 旋转图像 - 力扣（LeetCode）留一道巧思题，线性代数

链表

奇妙的题目：142. 环形链表 II - 力扣（LeetCode）

23. 合并 K 个升序链表 - 力扣（LeetCode）

这道题的归并思路非常牛逼，建议长期回溯一下：

/**
 * 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:
    ListNode* mergeTwoLists(ListNode *a, ListNode *b)
    {
        if(!a || !b) return a ? a : b;
        ListNode head;
        ListNode* tail = &head;
        while(a && b)
        {
            if(a->val < b->val)
            {
                tail->next = a;
                a = a->next;
            }
            else
            {
                tail->next = b;
                b = b->next;
            }
            tail = tail->next;
        }
        tail->next = a ? a : b;
        return head.next;
    }

    ListNode* merge(int l,int r,vector<ListNode*> &lists)
    {
        if(l == r)  return lists[l];
        if(l > r) return nullptr;
        //if((r - l) == 1) return mergeTwoLists(lists[l],lists[r]);
        int mid = l + (r - l)/2;
        return mergeTwoLists(merge(l,mid,lists),merge(mid+1,r,lists));
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(0,lists.size()-1,lists);
    }
};

二叉树

有一道题需要用到前缀和的思路：437. 路径总和 III - 力扣（LeetCode）

什么是前缀和？

前缀和是一种记录累积和的技术，通常用于快速计算某个区间的和。它的核心思想是：

  • 对于一个序列或路径，记录从起点到每个位置的累积和（前缀和）。
  • 如果需要计算从位置 i 到位置 j 的子区间和，只需用 prefixSum[j] - prefixSum[i-1] 即可。

在数组问题中，前缀和非常常见。例如：

  • 数组 [1, 2, 3, 4] 的前缀和是 [1, 3, 6, 10]。
  • 要计算索引 1 到 3 的子数组和（2 + 3 + 4），可以用 prefixSum[3] - prefixSum[0] = 10 - 1 = 9。

在二叉树中，前缀和的概念类似，但需要适应树的结构。我们记录从根节点到当前节点的路径和（前缀和），并利用这些前缀和来快速找到路径和等于目标值的子路径。

为什么在二叉树路径和问题中用前缀和？

你的问题（pathSum）要求找到二叉树中所有从任意节点到任意节点（沿路径向下）的连续路径，其和等于 targetSum。负数的存在使得滑动窗口方法失效，因为路径和可能忽大忽小，无法简单地通过弹出元素调整。

前缀和的优势在于：

  1. 通用性：它不依赖路径和的单调性，适用于正数、负数和零。
  2. 高效性：通过哈希表记录前缀和的出现次数，可以在 O(1) 时间内检查是否存在符合条件的子路径。
  3. 树结构适配：通过递归遍历树，动态维护路径上的前缀和。

前缀和在路径和问题中的核心思想

假设你在二叉树中从根节点走到当前节点，路径上的节点值依次为 [a, b, c, d]，当前路径和为 a + b + c + d。你想知道是否存在一个子路径（从某个祖先节点到当前节点），其和等于 targetSum。

  • 前缀和定义：从根到当前节点的路径和 currSum = a + b + c + d 是一个前缀和。

  • 子路径和：如果存在一个祖先节点，其到根的前缀和为 prefixSum，那么从该祖先到当前节点的子路径和为：

    currSum - prefixSum = targetSum

    即：

    prefixSum = currSum - targetSum

  • 哈希表记录：用一个哈希表 prefixSums 记录遍历过程中遇到的所有前缀和及其出现次数。如果 currSum - targetSum 出现在哈希表中，说明存在一条子路径的和等于 targetSum。

    class Solution {
    public:
        int pathSum(TreeNode* root, int targetSum) {
            unordered_map<long long, int> prefixSums; // 存储前缀和及其出现次数
            prefixSums[0] = 1; // 初始化：空路径的前缀和为0，出现1次
            return dfs(root, 0, targetSum, prefixSums);
        }

    private:
        int dfs(TreeNode* root, long long currSum, int targetSum, unordered_map<long long, int>& prefixSums) {
            if (!root) {
                return 0;
            }

            // 当前路径的前缀和
            currSum += root->val;

            // 检查是否存在前缀和使得 currSum - prefixSum == targetSum
            int count = prefixSums[currSum - targetSum];

            // 将当前前缀和加入哈希表
            prefixSums[currSum]++;

            // 递归处理左子树和右子树
            count += dfs(root->left, currSum, targetSum, prefixSums);
            count += dfs(root->right, currSum, targetSum, prefixSums);

            // 回溯：移除当前前缀和，因为当前路径不再使用
            prefixSums[currSum]--;

            return count;
        }
    };

一道非常经典的想着不难，码的时候很难：105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

class Solution {
private:
    unordered_map<int, int> index;

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        for(int i = 0; i < n; i++)
        {
            index[inorder[i]] = i;
        }
        return build(preorder,inorder,0,n-1,0,n-1);
    }

    TreeNode* build(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right)
    {
        if(preorder_left > preorder_right)
        {
            return nullptr;
        }

        int preorder_root = preorder_left;
        int inorder_root = index[preorder[preorder_left]];

        TreeNode* root = new TreeNode(preorder[preorder_left]);
        int size_left_subtree = inorder_root - inorder_left;

        root->left = build(preorder,inorder,preorder_left + 1, preorder_left + size_left_subtree, inorder_left,inorder_root - 1);

        root->right = build(preorder,inorder,preorder_left + size_left_subtree + 1,preorder_right, inorder_root + 1, inorder_right);

        return root;
    }
};

图论

回溯

主要是有一个标准的板子

在此记录一下（其实感觉不是很难）

题目出处：46. 全排列 - 力扣（LeetCode）

class Solution {
private:
    vector<vector<int>> res;
    vector<int> path;
public:
    void backtracking(vector<int>& nums, vector<bool>& used)
    {
        if (path.size() == nums.size())
        {
            res.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++)
        {
            if (used[i] == true)   //如果该元素被使用过了，则直接跳过
                continue;

            used[i] = true;        //下面要用，先标记上已使用
            path.push_back(nums[i]);
            backtracking(nums, used);
            path.pop_back();       //回溯path和used，即将本层的处理全部Ctrl + Z(撤销~~)
            used[i] = false;
        }
    }

    vector<vector<int>> permute(vector<int>& nums) 
    {
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return res;
    }
};

还有感觉时不时可以回忆一下n皇后：51. N 皇后 - 力扣（LeetCode）

把**行（row）**视为回溯推进的路标！

感觉重要的就是路标的标定和查找。

二分查找

感觉是因为自己有一个很笨笨的方法，导致写的每次逻辑都非常不通畅。

因此在此记录下两者区别：

题目出处：153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

官方题解：

class Solution {
public:
    int findMin(vector<int>& nums) {
        int low = 0;
        int high = nums.size() - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (nums[pivot] < nums[high]) {
                high = pivot;
            }
            else {
                low = pivot + 1;
            }
        }
        return nums[low];
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/solutions/698479/xun-zhao-xuan-zhuan-pai-xu-shu-zu-zhong-5irwp/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

我的铸币理解：

class Solution {
public:
    int findMin(vector<int>& nums) {
        if(nums.size() == 1)
            return nums[0];
        return find(0,nums.size()-1,nums);
    }

    int find(int left,int right,vector<int> nums)
    {
        int mid = (left + right)/2;
        if(left == right-1)
        {
            return nums[right] > nums[left] ? nums[left] : nums[right];
        }
        else if(nums[mid]<nums[left])
        {
            return find(left,mid,nums);
        }
        else if(nums[mid]>nums[right])
        {
            return find(mid,right,nums);
        }
        else
        {
            return nums[left];
        }
    }
};

其实要理解就是一个区间问题，可以再贴一个简明扼要的写法：

这个的理解永远是取[left,right]，永远都是闭区间，所以即便最后left == right依然是有意义的，如果此时未能找到，会进入最后一个循环返回-1，而且每次循环middle一定会缩减额外的1格。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size()-1;
        return search(left,right,nums,target);
    }
    
    int search(int left,int right, vector<int>& nums,int target)
    {
        if(left > right)
        {
            return -1;
        }
        int middle = left + (right - left)/2;
        if(nums[middle] < target)
        {
            return search(middle+1,right,nums,target);
        }
        else if(nums[middle] > target)
        {
            return search(left,middle-1,nums,target);
        }
        else
        {
            return middle;
        }
    }
};

然后有一道变种题，卡在最后一种情况很久很久：

33. 搜索旋转排序数组 - 力扣（LeetCode）

需要考虑以下题解中的<=号：

if(nums[middle] < target)
        {
            if(nums[right] < target && nums[middle] <= nums[right])
            {
                return deep(left,middle-1,nums,target);
            }
            else
            {
                return deep(middle+1,right,nums,target);
            }
            
        }
        else if(nums[middle] > target)
        {
            if(nums[left] > target && nums[left] <= nums[middle])
            {
                return deep(middle+1,right,nums,target);
            }
            else
            {
                return deep(left,middle-1,nums,target);
            } 
        }

栈

堆

贪心算法

嘶……

大部分贪心都被我用dp过去了……

不过这道倒是dp没想出来:

45. 跳跃游戏 II - 力扣（LeetCode）

动态规划

感觉没有想象中的那么恐怖，其实就是要找到一条可以表示所有情况的通式。

接着找到他的初状态就可以了。

最好是要常备草稿纸！

补充一道很有难度的动态规划，重点是考虑维护两个数组，主要是因为负数的特殊化以及0的特殊性！：

152. 乘积最大子数组 - 力扣（LeetCode）

多维动态规划

好难我去，需要准备好理解各个维度之间的关系，以及你为什么需要这个维度，这个维度在递推式中代表什么？

416. 分割等和子集 - 力扣（LeetCode）

上面这道题，背包问题，虽然是中等，但是对理解具象维度的含义非常有帮助，摘一下官方的题解：

创建二维数组 dp，包含 n 行 target+1 列，其中 dp[i][j] 表示从数组的 [0,i] 下标范围内选取若干个正整数（可以是 0 个），是否存在一种选取方案使得被选取的正整数的和等于 j。初始时，dp 中的全部元素都是 false。

作者：力扣官方题解
链接：https://leetcode.cn/problems/partition-equal-subset-sum/solutions/442320/fen-ge-deng-he-zi-ji-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

技巧

快慢指针套圈问题

异或求异

多数数字的相消

下一个排列->找到非降序，然后找到第一个比非降序数大的数交换位置->再对非降序数后的所有数字翻转