LeetCode经典算法题解详解本文汇总了常见的LeetCode算法题目及其C++解法，涵盖字符串、数组、链表、动态规划等多个知识点，适合算法面试准备和日常练习。
目录字符串处理数组问题链表操作动态规划树的遍历1. 字符串处理1.1 计数二进制子串（Count Binary Substrings）题目描述：给定一个字符串，统计连续的0和1数量相同的子串个数。
解题思路：
统计连续相同字符的分组长度相邻两组可以形成的子串数量为两者的最小值例如："00111"分组为[2,3]，可形成min(2,3)=2个子串代码实现：
int countBinarySubstrings(string s) {
vector
s += ' '; // 添加哨兵，方便处理最后一组
int ssize = s.size();
int num = 0;
// 统计每组连续相同字符的数量
for (int i = 0; i < ssize - 1; i++) {
if (s[i] == s[i + 1]) {
num++;
} else {
num++;
v.push_back(num);
num = 0;
}
}
// 计算相邻两组能形成的子串数
int res = 0;
for (int i = 1; i < v.size(); i++) {
res += min(v[i-1], v[i]);
}
return res;
}
时间复杂度：O(n)空间复杂度：O(n)
1.2 无重复字符的最长子串（Longest Substring Without Repeating Characters）题目描述：找出给定字符串中不含重复字符的最长子串长度。
解题思路：
使用滑动窗口+哈希集合右指针不断扩展窗口，遇到重复字符时左指针收缩维护最大窗口长度代码实现：
#include
#include
using namespace std;
int lengthOfLongestSubstring(string s) {
unordered_set
int n = s.size();
int left = 0, right = 0;
int maxLen = 0;
while (right < n) {
if (st.count(s[right]) == 0) {
st.insert(s[right]);
maxLen = max(maxLen, right - left + 1);
right++;
} else {
st.erase(s[left]);
left++;
}
}
return maxLen;
}
时间复杂度：O(n)空间复杂度：O(min(n, m))，m为字符集大小
1.3 最长回文子串（Longest Palindromic Substring）题目描述：找出字符串中最长的回文子串。
解题思路：
中心扩展法：以每个字符为中心向两边扩展需要考虑奇数长度和偶数长度两种情况记录最长回文的起始位置和长度代码实现：
string longestPalindrome(string s) {
int start = 0, end = 0;
int len = 0;
int l = 0;
for (int i = 0; i < s.size() - 1; i++) {
// 奇数长度回文（中心为单个字符）
start = i;
end = i;
while (start >= 0 && end < s.size() && s[start] == s[end]) {
start--;
end++;
}
if (end - start - 2 > len) {
len = end - start - 1;
l = start + 1;
}
// 偶数长度回文（中心为两个字符）
start = i;
end = i + 1;
while (start >= 0 && end < s.size() && s[start] == s[end]) {
start--;
end++;
}
if (end - start - 2 > len) {
len = end - start - 1;
l = start + 1;
}
}
return s.substr(l, len);
}
时间复杂度：O(n²)空间复杂度：O(1)
2. 数组问题2.1 两数之和（Two Sum）题目描述：在数组中找到两个数，使其和等于目标值。
解题思路：
使用哈希表存储已遍历的数字及其索引对于当前数字，查找target - nums[i]是否存在一次遍历即可完成代码实现：
vector
unordered_map
for (int i = 0; i < nums.size(); i++) {
if (mp.find(target - nums[i]) != mp.end()) {
return {mp[target - nums[i]], i};
} else {
mp[nums[i]] = i;
}
}
return {};
}
时间复杂度：O(n)空间复杂度：O(n)
2.2 三数之和（Three Sum）题目描述：找出数组中所有和为0的三元组。
解题思路：
先对数组排序固定第一个数，用双指针找另外两个数注意去重：跳过重复的元素代码实现：
vector
int n = nums.size();
sort(nums.begin(), nums.end());
vector
for (int i = 0; i < n; i++) {
// 跳过重复元素
if (i > 0 && nums[i] == nums[i - 1]) continue;
// 双指针，目标是找到 nums[l] + nums[r] = -nums[i]
int l = i + 1, r = n - 1;
int target = -nums[i];
while (l < r) {
int sum = nums[l] + nums[r];
if (sum == target) {
ans.push_back({nums[i], nums[l], nums[r]});
l++;
r--;
// 跳过重复元素
while (l < r && nums[l] == nums[l - 1]) l++;
while (l < r && nums[r] == nums[r + 1]) r--;
} else if (sum < target) {
l++;
} else {
r--;
}
}
}
return ans;
}
时间复杂度：O(n²)空间复杂度：O(1)（不计返回值）
2.3 最大子数组和（Maximum Subarray）题目描述：找到数组中和最大的连续子数组。
方法一：动态规划（Kadane算法）解题思路：
dp[i]表示以nums[i]结尾的最大子数组和状态转移：dp[i] = max(nums[i], dp[i-1] + nums[i])可以优化为O(1)空间代码实现：
int maxSubArray(vector
int maxSum = nums[0];
int pre = nums[0];
for (int i = 1; i < nums.size(); i++) {
pre = (pre + nums[i] < nums[i]) ? nums[i] : pre + nums[i];
maxSum = (maxSum > pre) ? maxSum : pre;
}
return maxSum;
}
时间复杂度：O(n)空间复杂度：O(1)
方法二：分治法解题思路：
将数组分为左右两部分最大子数组可能在：左半部分、右半部分、跨越中点递归求解并合并结果代码实现：
struct Status {
int lSum; // 包含左边界的最大子数组和
int rSum; // 包含右边界的最大子数组和
int iSum; // 区间总和
int mSum; // 区间最大子数组和
};
Status get(vector
if (l == r) {
return (Status){a[l], a[l], a[l], a[l]};
}
int m = (l + r) >> 1;
Status lSub = get(a, l, m);
Status rSub = get(a, m + 1, r);
int iSum = lSub.iSum + rSub.iSum;
int lSum = max(lSub.lSum, lSub.iSum + rSub.lSum);
int rSum = max(rSub.rSum, rSub.iSum + lSub.rSum);
int mSum = max(max(lSub.mSum, rSub.mSum), lSub.rSum + rSub.lSum);
return (Status){lSum, rSum, mSum, iSum};
}
int maxSubArray(vector
return get(nums, 0, nums.size() - 1).mSum;
}
时间复杂度：O(n log n)空间复杂度：O(log n)
2.4 第K大元素（Kth Largest Element）题目描述：找出数组中第K大的元素。
解题思路：
使用快速选择算法（Quick Select）第K大等价于第(n-k)小快排的partition过程，不需要完全排序代码实现：
int quicksort(vector
int pivot = nums[r]; // 选最右边为基准
int i = l; // 小于区的右边界
for (int j = l; j < r; ++j) {
if (nums[j] < pivot) {
swap(nums[i++], nums[j]);
}
}
swap(nums[i], nums[r]); // 把基准放到中间
return i; // 返回基准位置
}
int findKthLargest(vector
int l = 0, r = nums.size() - 1;
int n = quicksort(nums, l, r);
// 第k大 = 第(size-k)小
while (n != nums.size() - k) {
if (n < nums.size() - k) {
l = n + 1;
} else {
r = n - 1;
}
n = quicksort(nums, l, r);
}
return nums[n];
}
时间复杂度：平均O(n)，最坏O(n²)空间复杂度：O(1)
2.5 合并区间（Merge Intervals）题目描述：合并所有重叠的区间。
解题思路：
先按左端点排序遍历区间，判断当前区间能否与上一个合并能合并则更新右边界，否则加入结果并开启新段代码实现：
vector
if (intervals.empty()) return {};
// 按左端点升序排序
sort(intervals.begin(), intervals.end(),
[](const vector
return a[0] < b[0];
});
vector
int l = intervals[0][0], r = intervals[0][1];
for (size_t i = 1; i < intervals.size(); ++i) {
// 能合并：当前区间左端点 <= 当前合并段的右端点
if (intervals[i][0] <= r) {
r = max(r, intervals[i][1]);
} else {
// 不能合并，把旧段加入结果
res.push_back({l, r});
l = intervals[i][0];
r = intervals[i][1];
}
}
res.push_back({l, r}); // 最后一段
return res;
}
时间复杂度：O(n log n)空间复杂度：O(log n)（排序栈空间）
2.6 买卖股票的最佳时机（Best Time to Buy and Sell Stock）题目描述：只能买卖一次，求最大利润。
解题思路：
维护当前最低价格遍历时计算当前价格卖出的利润更新最大利润代码实现：
int maxProfit(vector
int cost = prices[0];
int profit = 0;
for (int i = 1; i < prices.size(); i++) {
cost = min(cost, prices[i]);
profit = max(profit, prices[i] - cost);
}
return profit;
}
时间复杂度：O(n)空间复杂度：O(1)
2.7 合并两个有序数组（Merge Sorted Array）题目描述：将nums2合并到nums1中（nums1有足够空间）。
解题思路：
从后往前填充，避免覆盖未处理元素双指针分别指向两个数组的末尾比较并将较大值放到nums1末尾代码实现：
void merge(vector
int i1 = m - 1;
int i2 = n - 1;
for (int i = m + n - 1; i >= 0; i--) {
if (i2 < 0 || (i1 >= 0 && nums1[i1] >= nums2[i2])) {
nums1[i] = nums1[i1--];
} else {
nums1[i] = nums2[i2--];
}
}
}
时间复杂度：O(m + n)空间复杂度：O(1)
3. 链表操作3.1 反转链表（Reverse Linked List）题目描述：反转一个单链表。
解题思路：
使用三个指针：prev、curr、next迭代地修改每个节点的next指向最后返回新的头节点代码实现：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
};
时间复杂度：O(n)空间复杂度：O(1)
3.2 合并两个有序链表（Merge Two Sorted Lists）题目描述：合并两个升序链表为一个新的升序链表。
解题思路：
使用递归方法比较两个链表头节点，选择较小的递归处理剩余节点代码实现：
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (list1 == nullptr || list2 == nullptr) {
return list1 == nullptr ? list2 : list1;
}
if (list1->val < list2->val) {
list1->next = mergeTwoLists(list1->next, list2);
return list1;
} else {
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}
};
时间复杂度：O(m + n)空间复杂度：O(m + n)（递归栈）
4. 动态规划4.1 硬币兑换（Coin Change）题目描述：用最少的硬币数凑成目标金额。
方法一：完全背包DP解题思路：
dp[i]表示凑成金额i的最少硬币数状态转移：dp[i] = min(dp[i], dp[i - coin] + 1)初始化dp[0] = 0，其余为无穷大代码实现：
class Solution {
public:
int coinChange(vector
int Max = amount + 1;
vector
dp[0] = 0;
for (int i = 1; i <= amount; ++i) {
for (int j = 0; j < coins.size(); ++j) {
if (coins[j] <= i) {
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
};
时间复杂度：O(amount × n)空间复杂度：O(amount)
方法二：优化版本代码实现：
int coinChange(vector
vector
dp[0] = 0;
// 预处理：单个硬币能直接凑成的金额
for (int i = 0; i < coins.size() && coins[i] <= amount; i++) {
dp[coins[i]] = 1;
}
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.size(); j++) {
if (i - coins[j] > 0 && dp[i] > dp[i - coins[j]] + 1) {
dp[i] = dp[i - coins[j]] + 1;
}
}
}
return dp[amount] == 100000 ? -1 : dp[amount];
}
5. 树的遍历5.1 二叉树的层序遍历（Binary Tree Level Order Traversal）题目描述：按层输出二叉树的节点值。
解题思路：
使用队列进行BFS记录每层节点数量，分层处理将每层节点值存入结果数组代码实现：
vector
vector
queue
if (root != nullptr) {
q1.push(root);
}
while (!q1.empty()) {
int size = q1.size();
vector
for (int i = 0; i < size; i++) {
TreeNode* current = q1.front();
q1.pop();
if (current->left) {
q1.push(current->left);
}
if (current->right) {
q1.push(current->right);
}
v.push_back(current->val);
}
res.push_back(v);
}
return res;
}
时间复杂度：O(n)空间复杂度：O(n)
总结本文涵盖了常见的算法题型和解题技巧：
字符串：滑动窗口、中心扩展数组：双指针、哈希表、快速选择链表：双指针、递归动态规划：状态定义与转移树：BFS层序遍历这些题目是面试高频考点，建议：
理解每种算法的核心思想注意边界条件处理分析时间和空间复杂度多做类似题目加深理解祝大家刷题顺利，offer多多！