昨天 10:22 浙江大学算法工程师发布于上海

关注

C++面试必备算法题汇总

一、数组与双指针（Two Pointers）

核心思想

通过两个指针在数组中移动，降低时间复杂度（通常从 O(n²) → O(n)）

1. 两数之和（变种极多）

经典题：Two Sum

思路：

哈希表记录已遍历元素
时间复杂度 O(n)

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> mp;
    for (int i = 0; i < nums.size(); i++) {
        int diff = target - nums[i];
        if (mp.count(diff)) return {mp[diff], i};
        mp[nums[i]] = i;
    }
    return {};
}

2. 三数之和（排序 + 双指针）

关键点：

排序
固定一个数 + 双指针逼近

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    
    for (int i = 0; i < nums.size(); i++) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        
        int l = i + 1, r = nums.size() - 1;
        while (l < r) {
            int sum = nums[i] + nums[l] + nums[r];
            if (sum == 0) {
                res.push_back({nums[i], nums[l], nums[r]});
                while (l < r && nums[l] == nums[l+1]) l++;
                while (l < r && nums[r] == nums[r-1]) r--;
                l++; r--;
            } else if (sum < 0) l++;
            else r--;
        }
    }
    return res;
}

二、滑动窗口（Sliding Window）

核心思想

维护一个动态区间，适用于子数组 / 子串问题

1. 最长无重复子串

int lengthOfLongestSubstring(string s) {
    unordered_set<char> st;
    int l = 0, res = 0;
    
    for (int r = 0; r < s.size(); r++) {
        while (st.count(s[r])) {
            st.erase(s[l++]);
        }
        st.insert(s[r]);
        res = max(res, r - l + 1);
    }
    return res;
}

2. 最小覆盖子串（困难高频）

核心：

双 map
满足条件才收缩窗口

三、链表（Linked List）

1. 反转链表

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    while (head) {
        ListNode* next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

2. 快慢指针（Floyd 判环）

应用：

判断是否有环
找环入口

bool hasCycle(ListNode *head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

C++面试常考题目类型都放入了专栏了：https://www.nowcoder.com/creation/manager/columnDetail/Mq7XWW

四、二叉树（Tree）

本质：递归 + 分治

1. 前中后序遍历（必须手写）

void preorder(TreeNode* root) {
    if (!root) return;
    cout << root->val;
    preorder(root->left);
    preorder(root->right);
}

2. 层序遍历（BFS）

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res;
    
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        int sz = q.size();
        vector<int> level;
        
        while (sz--) {
            auto node = q.front(); q.pop();
            level.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        res.push_back(level);
    }
    return res;
}

3. 最近公共祖先（LCA）

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    
    auto left = lowestCommonAncestor(root->left, p, q);
    auto right = lowestCommonAncestor(root->right, p, q);
    
    if (left && right) return root;
    return left ? left : right;
}

五、堆与优先队列（Heap）

典型题：Top K 问题

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int,int> cnt;
    for (int n : nums) cnt[n]++;
    
    priority_queue<pair<int,int>> pq;
    for (auto& [num, c] : cnt) {
        pq.push({c, num});
    }
    
    vector<int> res;
    while (k--) {
        res.push_back(pq.top().second);
        pq.pop();
    }
    return res;
}

六、动态规划（DP）

核心三步：

状态定义
状态转移
初始化

1. 爬楼梯（入门）

int climbStairs(int n) {
    vector<int> dp(n+1);
    dp[1] = 1; dp[2] = 2;
    for (int i = 3; i <= n; i++)
        dp[i] = dp[i-1] + dp[i-2];
    return dp[n];
}

2. 最长递增子序列（LIS）

O(n log n) 解法（面试加分项）

int lengthOfLIS(vector<int>& nums) {
    vector<int> dp;
    for (int num : nums) {
        auto it = lower_bound(dp.begin(), dp.end(), num);
        if (it == dp.end()) dp.push_back(num);
        else *it = num;
    }
    return dp.size();
}

3. 0-1 背包（经典模板）

for (int i = 0; i < n; i++) {
    for (int j = W; j >= w[i]; j--) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

七、回溯（Backtracking）

本质：暴力搜索 + 剪枝

1. 全排列

void backtrack(vector<int>& nums, vector<int>& path, vector<bool>& used) {
    if (path.size() == nums.size()) {
        res.push_back(path);
        return;
    }
    
    for (int i = 0; i < nums.size(); i++) {
        if (used[i]) continue;
        used[i] = true;
        path.push_back(nums[i]);
        backtrack(nums, path, used);
        path.pop_back();
        used[i] = false;
    }
}

八、图论（Graph）

1. DFS / BFS 模板

void dfs(int u) {
    visited[u] = true;
    for (int v : graph[u]) {
        if (!visited[v]) dfs(v);
    }
}

2. 拓扑排序（Topological Sort）

Kahn 算法：

queue<int> q;
for (...) if (in_degree[i] == 0) q.push(i);

while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : graph[u]) {
        if (--in_degree[v] == 0)
            q.push(v);
    }
}

3. 最短路径（Dijkstra）

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
pq.push({0, start});

while (!pq.empty()) {
    auto [dist, u] = pq.top(); pq.pop();
    for (auto [v, w] : graph[u]) {
        if (dist + w < d[v]) {
            d[v] = dist + w;
            pq.push({d[v], v});
        }
    }
}