【LeetCode】力扣刷题热题100道（1-5题）附源码 链表 子串 中位数 回文子串（C++）

目录

1.两数之和

2.两数相加-链表

3.无重复字符的最长子串

4.寻找两个正序数组的中位数

5.最长回文子串

---

1.两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

第一种方法比较常规暴力枚举，时间复杂度： O(n^2)，因为我们使用双重循环遍历数组，每次检查一对元素的和。

class Solution {
public:vector<int> twoSum(vector<int>& 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 {};}
};

 第二种方法哈希表解法，时间复杂度： O(n)，因为我们只遍历一次数组，对于每个元素的查找和插入操作，哈希表的时间复杂度是常数 O(1)。

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> num_map;for (int i = 0; i < nums.size(); ++i) {int complement = target - nums[i]; if (num_map.find(complement) != num_map.end()){return {num_map[complement], i};}num_map[nums[i]] = i;}return {};}
};

假设 nums = [2, 7, 11, 15]，目标值 target = 9。

第一轮：

当前元素是 nums[0] = 2，计算 complement = 9 - 2 = 7。
哈希表 num_map 为空，7 不在哈希表中。
将当前元素 nums[0] = 2 存入哈希表：num_map = {2: 0}。
第二轮：

当前元素是 nums[1] = 7，计算 complement = 9 - 7 = 2。
哈希表 num_map = {2: 0}，发现 complement = 2 在哈希表中，说明 nums[0] + nums[1] = 9。
返回结果：{0, 1}。
如何用哈希表来找到两个数？
问题的核心思想： 对于每一个元素 nums[i]，我们希望在之前遍历的数组元素中，找到一个数 complement，使得 nums[i] + complement = target，从而满足题目条件。也就是：

complement=target−nums[i]\text{complement} = \text{target} - \text{nums}[i]complement=target−nums[i]
这样，我们就可以通过查找哈希表中是否存在 complement 来判断是否找到了匹配的两个数。

为什么哈希表有效？

哈希表是一个常数时间查找结构： 使用哈希表存储之前遍历过的元素，每个元素和其下标都作为键值对存储。查找一个元素是否在哈希表中存在的时间复杂度为 O(1)。
早期发现匹配： 在遍历数组时，我们可以在当前元素 nums[i] 被处理之前，检查 target - nums[i] 是否已经出现在哈希表中。这样，查找操作变得非常高效，我们能快速确定某个值是否已经出现在数组的前面部分。
解释为什么能找到配对：

思考过程： 对于每一个元素 nums[i]，我们在遍历过程中都计算出当前元素和目标值的差值 complement = target - nums[i]。然后我们查找哈希表中是否存在 complement，如果存在，就说明存在两个数，它们的和为 target。
哈希表的作用： 哈希表的作用是记录我们已经遍历过的元素，所以当我们遇到某个元素时，我们只需要查找它的差值是否已经存在。这样就可以快速找到一对数。
为什么可以在 O(n) 时间内找到答案：一遍扫描： 在遍历数组时，我们只需要对每个元素进行一次查找和插入操作，且每次查找和插入的时间复杂度是常数 O(1)。
不需要重复扫描： 不像暴力解法需要两层循环去遍历数组的每一对元素，哈希表方法只需要遍历一次数组。

2.两数相加-链表

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

/*** 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* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode *head = new ListNode(0);ListNode *current = head;int carry = 0;while(l1 != nullptr || l2 != nullptr || carry != 0){int data1 = (l1 != nullptr) ? l1->val : 0;int data2 = (l2 != nullptr) ? l2->val : 0;int sum = data1 + data2 + carry;carry = sum / 10;current->next = new ListNode(sum % 10);current=current->next;if(l1 != nullptr) l1 = l1->next;if(l2 != nullptr) l2 = l2->next;}return head->next;}   
};

该 while 循环继续执行，直到两个链表都遍历完且没有进位。也就是说：

如果 l1 和 l2 都为空，但 carry 不为零（即最后一次加法有进位），我们仍然需要处理进位。
在每次循环中，我们从 l1 和 l2 中提取当前节点的值（如果节点为空则默认为 0）。
然后，将两个节点的值和进位相加，得到当前位的和。
使用 sum / 10 计算进位，sum % 10 作为当前位的结果。
将当前位的结果存入新节点，并更新 current 指针。

3.无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
（子字符串 是字符串中连续的 非空 字符序列）

​

class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_set<char> char_set; int left = 0;  int max_len = 0; for (int right = 0; right < s.size(); ++right) {while (char_set.find(s[right]) != char_set.end()) {char_set.erase(s[left]);left++;}char_set.insert(s[right]);max_len = max(max_len, right - left + 1);}return max_len;}
};

我们来针对输入 "abcabcbb"这个测试用例来讲解，如下所示：
初始化
char_set: 是一个 unordered_set，用于存储当前窗口内的字符，确保窗口内的字符是唯一的。
left: 左指针，初始值为 0，表示窗口的左边界。
max_len: 用于记录最长无重复子串的长度，初始值为 0。
遍历字符串
我们通过 right 指针从左到右遍历字符串 s，并不断更新 max_len。

输入字符串为 "abcabcbb"，其长度为 8。我们按每次循环逐步分析。

第 1 次循环 (right = 0)
当前字符 s[right] = 'a'。
检查 char_set 是否包含 'a'，char_set.find('a') 返回 char_set.end()，说明没有重复字符。
将 'a' 插入到 char_set 中：char_set = {'a'}。
计算当前窗口的长度 right - left + 1 = 0 - 0 + 1 = 1，更新 max_len = max(0, 1) = 1。
第 2 次循环 (right = 1)
当前字符 s[right] = 'b'。
检查 char_set 是否包含 'b'，char_set.find('b') 返回 char_set.end()，说明没有重复字符。
将 'b' 插入到 char_set 中：char_set = {'a', 'b'}。
计算当前窗口的长度 right - left + 1 = 1 - 0 + 1 = 2，更新 max_len = max(1, 2) = 2。
第 3 次循环 (right = 2)
当前字符 s[right] = 'c'。
检查 char_set 是否包含 'c'，char_set.find('c') 返回 char_set.end()，说明没有重复字符。
将 'c' 插入到 char_set 中：char_set = {'a', 'b', 'c'}。
计算当前窗口的长度 right - left + 1 = 2 - 0 + 1 = 3，更新 max_len = max(2, 3) = 3。
第 4 次循环 (right = 3)
当前字符 s[right] = 'a'。
检查 char_set 是否包含 'a'，char_set.find('a') 返回非 char_set.end()，说明有重复字符。
进入 while 循环，开始调整窗口的左边界 left：
移除 s[left] = 'a' 从 char_set 中：char_set = {'b', 'c'}。
左指针右移：left = 1。
继续检查 char_set 是否包含 'a'，此时不再包含 'a'。
将 'a' 插入到 char_set 中：char_set = {'b', 'c', 'a'}。
计算当前窗口的长度 right - left + 1 = 3 - 1 + 1 = 3，max_len 不变，仍为 3。
第 5 次循环 (right = 4)
当前字符 s[right] = 'b'。
检查 char_set 是否包含 'b'，char_set.find('b') 返回非 char_set.end()，说明有重复字符。
进入 while 循环，开始调整窗口的左边界 left：
移除 s[left] = 'b' 从 char_set 中：char_set = {'c', 'a'}。
左指针右移：left = 2。
继续检查 char_set 是否包含 'b'，此时不再包含 'b'。
将 'b' 插入到 char_set 中：char_set = {'c', 'a', 'b'}。
计算当前窗口的长度 right - left + 1 = 4 - 2 + 1 = 3，max_len 不变，仍为 3。
第 6 次循环 (right = 5)
当前字符 s[right] = 'c'。
检查 char_set 是否包含 'c'，char_set.find('c') 返回非 char_set.end()，说明有重复字符。
进入 while 循环，开始调整窗口的左边界 left：
移除 s[left] = 'c' 从 char_set 中：char_set = {'a', 'b'}。
左指针右移：left = 3。
继续检查 char_set 是否包含 'c'，此时不再包含 'c'。
将 'c' 插入到 char_set 中：char_set = {'a', 'b', 'c'}。
计算当前窗口的长度 right - left + 1 = 5 - 3 + 1 = 3，max_len 不变，仍为 3。
第 7 次循环 (right = 6)
当前字符 s[right] = 'b'。
检查 char_set 是否包含 'b'，char_set.find('b') 返回非 char_set.end()，说明有重复字符。
进入 while 循环，开始调整窗口的左边界 left：
移除 s[left] = 'a' 从 char_set 中：char_set = {'b', 'c'}。
左指针右移：left = 4。
继续检查 char_set 是否包含 'b'，此时不再包含 'b'。
将 'b' 插入到 char_set 中：char_set = {'b', 'c'}。
计算当前窗口的长度 right - left + 1 = 6 - 4 + 1 = 3，max_len 不变，仍为 3。
第 8 次循环 (right = 7)
当前字符 s[right] = 'b'。
检查 char_set 是否包含 'b'，char_set.find('b') 返回非 char_set.end()，说明有重复字符。
进入 while 循环，开始调整窗口的左边界 left：
移除 s[left] = 'b' 从 char_set 中：char_set = {'c'}。
左指针右移：left = 5。
继续检查 char_set 是否包含 'b'，此时不再包含 'b'。
将 'b' 插入到 char_set 中：char_set = {'c', 'b'}。
计算当前窗口的长度 right - left + 1 = 7 - 5 + 1 = 3，max_len 不变，仍为 3。

4.寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (m+n)) 。

​

方法一：（不推荐）

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {vector<int> merged;double median = 0;int i=0,j=0;while(i < nums1.size() && j < nums2.size()){if(nums1[i] < nums2[j]){merged.push_back(nums1[i]);i++;} else {merged.push_back(nums2[j]);j++;}}while (i < nums1.size()) {merged.push_back(nums1[i]);i++;}while(j < nums2.size()){merged.push_back(nums2[j]);j++;}int n = merged.size();if (n % 2 == 0) {median = (merged[n / 2 - 1] + merged[n / 2]) / 2.0;} else {median = merged[n / 2];}return median;}
};

使用双指针 i 和 j 分别指向 nums1 和 nums2 的起始位置。
比较 nums1[i] 和 nums2[j]，将较小的元素放入 merged 数组。
将较小元素的指针后移（即，继续检查数组中的下一个元素）。
直到一个数组被完全遍历。
如果 nums1 还有剩余元素，将其直接追加到 merged 中。
同样地，如果 nums2 还有剩余元素，也直接追加到 merged 中。
这样，merged 就是一个完整的、合并后的有序数组。
首先获取 merged 数组的大小 n。
如果 n 是偶数：
中位数是数组中间两个数的平均值，即 (merged[n / 2 - 1] + merged[n / 2]) / 2.0。
如果 n 是奇数：
中位数是数组的中间元素，即 merged[n / 2]。
方法二：

​

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {// 确保 nums1 是较短的数组if (nums1.size() > nums2.size()) {return findMedianSortedArrays(nums2, nums1);}int m = nums1.size();int n = nums2.size();int totalLeft = (m + n + 1) / 2;int left = 0, right = m;while (left < right) {int i = left + (right - left) / 2;int j = totalLeft - i;if (nums1[i] < nums2[j - 1]) {// i 需要右移left = i + 1;} else {// i 需要左移right = i;}}int i = left;int j = totalLeft - i;// 左半部分的最大值int nums1LeftMax = (i == 0) ? INT_MIN : nums1[i - 1];int nums2LeftMax = (j == 0) ? INT_MIN : nums2[j - 1];int leftMax = max(nums1LeftMax, nums2LeftMax);// 如果总长度是奇数if ((m + n) % 2 == 1) {return leftMax;}// 右半部分的最小值int nums1RightMin = (i == m) ? INT_MAX : nums1[i];int nums2RightMin = (j == n) ? INT_MAX : nums2[j];int rightMin = min(nums1RightMin, nums2RightMin);// 如果总长度是偶数，返回平均值return (leftMax + rightMin) / 2.0;}
};

1. 确保 nums1 是较短的数组
通过判断 nums1 和 nums2 的长度，始终在较短的数组上进行二分查找。

2. 使用二分查找调整分割点
i 是在 nums1 的分割点，j 是在 nums2 的分割点。
i + j = totalLeft，保证左半部分元素总数等于右半部分。
根据条件调整 i：
如果 nums1[i] < nums2[j - 1]，说明 i 需要右移。
如果 nums1[i] >= nums2[j - 1]，说明 i 满足条件或需要左移。
3. 计算中位数
左半部分最大值为：max(nums1[i-1], nums2[j-1])。
右半部分最小值为：min(nums1[i], nums2[j])。
如果总长度为奇数，直接返回左半部分最大值。
如果总长度为偶数，返回左右半部分最大值与最小值的平均值。

5.最长回文子串

给你一个字符串 s，找到 s 中最长的 回文子串。

回文性
如果字符串向前和向后读都相同，则它满足 回文性子字符串
子字符串 是字符串中连续的 非空 字符序列。

​

动态规划法

class Solution {
public:string longestPalindrome(string s) {int n = s.size();if (n <= 1) return s;vector<vector<bool>> dp(n, vector<bool>(n, false));int start = 0, maxLen = 1;for (int i = 0; i < n; ++i) dp[i][i] = true;for (int i = 0; i < n - 1; ++i) {if (s[i] == s[i + 1]) {dp[i][i + 1] = true;start = i;maxLen = 2;}}for (int len = 3; len <= n; ++len) {for (int i = 0; i + len - 1 < n; ++i) {int j = i + len - 1;if (s[i] == s[j] && dp[i + 1][j - 1]) {dp[i][j] = true;start = i;maxLen = len;}}}return s.substr(start, maxLen);}
};

首先，我们获取字符串 s 的长度 n。如果字符串长度小于或等于 1，则字符串本身就是回文的（单个字符本身就是回文），直接返回字符串。

dp 是一个二维布尔型数组，dp[i][j] 用来表示子串 s[i...j] 是否为回文串。数组大小为 n x n，初始化为 false。

每个单字符子串（即 s[i...i]）自然是回文的，因此将 dp[i][i] 设置为 true。

接下来，我们处理长度为 2 的子串。如果 s[i] == s[i+1]，那么 s[i...i+1] 是回文串，设置 dp[i][i+1] = true。此时，我们还更新 start 和 maxLen，记录最长回文子串的起始位置和长度。

从长度为 3 的子串开始，我们逐步扩展到更长的回文子串。具体来说，len 表示当前子串的长度，从 3 一直增加到 n。

对于每个长度为 len 的子串，我们通过以下条件判断是否为回文：

s[i] == s[j]：当前子串的首尾字符相同。
dp[i+1][j-1]：即子串 s[i+1...j-1] 是否是回文。
如果这两个条件都成立，那么 s[i...j] 也是回文子串，更新 dp[i][j] = true，并更新 start 和 maxLen，记录当前最长回文子串的起始位置和长度。

输入字符串 s = "babad"：

长度为 1 的子串：我们从一开始就知道每个单独的字符都是一个回文子串，所以 dp[i][i] = true 对于所有 i 都成立。对于 s = "babad"，初始化时，dp 数组是这样的：
dp = [ [true, false, false, false, false], [false, true, false, false, false], [false, false, true, false, false], [false, false, false, true, false], [false, false, false, false, true] ]

长度为 2 的子串：接着，代码检查相邻的字符是否相同。如果相同，设置 dp[i][i+1] = true。在 s = "babad" 中，s[0] != s[1]（b != a），s[1] != s[2]（a != b），s[2] != s[3]（b != a），s[3] != s[4]（a != d）。所以 dp 数组没有更新。
dp 仍然是：

dp = [ [true, false, false, false, false], [false, true, false, false, false], [false, false, true, false, false], [false, false, false, true, false], [false, false, false, false, true] ]

长度为 3 及以上的回文子串：接着，程序检查长度为 3 及以上的子串，逐步扩展回文子串的长度。对每一个 len（长度从 3 到 n），我们依次检查每个子串的起始位置 i。

当 len = 3 时：

对于 s[0...2] = "bab"，s[0] == s[2]（b == b），并且 dp[1][1] = true（即 "a" 是回文）。所以 dp[0][2] = true，start = 0，maxLen = 3。
现在 dp 数组更新为：
dp = [ [true, false, true, false, false], [false, true, false, false, false], [false, false, true, false, false], [false, false, false, true, false], [false, false, false, false, true] ]

这时，我们已经找到了 "bab" 作为一个回文子串。

继续检查更长的回文子串：当 len = 4 时：
对于 s[1...4] = "abad"，s[1] != s[4]（a != d），所以 dp[1][4] 不会被设置。
当 len = 5 时：
对于 s[0...4] = "babad"，s[0] != s[4]（b != d），所以 dp[0][4] 也不会被设置。
经过这些步骤，程序最终会返回最长的回文子串 "bab"，因为 start = 0 和 maxLen = 3。