1--两数之和
讲解参考：LeetCode 最热门 100 题
主要思路：
对数组进行从小到大的排序，使用两个指针指向第一个元素和最后一个元素，即左指针指向第一个元素A[l]，右指针指向最后一个元素A[R]；
判断两个指针当前指向值的和，若 A[l] + A[R] == Target，则返回；
若 A[l] + A[R] < Target，表明和较小，需要左指针右移，即 l++;
若 A[l] + A[R] > Target，表明和较大，需要右指针左移，即 r--;
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int n = nums.size();std::vector<int> idx;for(int i = 0; i < n; i++) idx.push_back(i);// 通过排序数组 idx 间接排序 numssort(idx.begin(), idx.end(), [idx, nums](int i, int j){return nums[idx[i]] < nums[idx[j]];});std::vector<int> rec;for(int l = 0, r = n - 1; l < n; ){if(nums[idx[l]] + nums[idx[r]] == target){rec.push_back(idx[l]);rec.push_back(idx[r]);break;}else if(nums[idx[l]] + nums[idx[r]] < target){l++;}else{r--;}}return rec;}
};2--两数相加
主要思路：
按位相加，用一个 carry 变量记录进位值，用一个 sum 变量记录加和值，不断遍历相加直到链表为空；
新建一个链表记录每个节点的加和值；
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode * H = new ListNode(); // 新建链表存储计算结果ListNode * ptr = H; // 当前指针int carry = 0; // 进位值初始化为0while(l1 || l2 || carry){ // 链表不为空且进位值不为0int sum = 0;if(l1){sum += l1->val;l1 = l1->next; }if(l2){sum += l2->val;l2 = l2->next;}sum += carry; // 累计上一轮的进位值 carry = sum / 10; // 更新进位值ListNode *node = new ListNode(); // 新建节点存储加和node->val = sum % 10;ptr->next = node; ptr = ptr->next;}return H->next; // 返回不带头结点的链表}
};3--无重复字符的最长子串
主要思路：
基于滑动窗口和哈希表，用一个滑动窗口遍历字符串的字符，确保滑动窗口内的所有字符都是不重复的，当滑动字符不断扩大遇到重复字符时，将左指针右移，直到没有重复字符，这时比较滑动窗口的长度和最大长度的值，更新最大长度；
用哈希表记录滑动窗口内一个字符出现的次数，当新字符进入时，新字符对应的出现次数加1，当滑动窗口离开字符时，字符对应的出现次数减1；
class Solution {
public:int lengthOfLongestSubstring(string s) {int len = s.length(); // 字符串的长度 int l = 0; // 滑动窗口的左指针std::unordered_map<char, int> count; // 记录当前滑动窗口 char 字符对应的个数（出现的次数）int max_len = 0; // 返回的最大长度for(int r = 0; r < len; r++){ // r表示滑动窗口的右指针count[s[r]]++; // s[r]字符对应的数目加1while(count[s[r]] > 1){ // 滑动窗口内出现重复字符count[s[l]]--; // 左指针准备右移，先将当前左指针对应的字符数量减1l++; // 左指针右移}max_len = std::max(max_len, r - l + 1);}return max_len;}
};4--寻找两个正序数组的中位数
主要思路：二分递归，视频讲解参考
#include <vector>
#include <iostream>class Solution {
public:int findKth(std::vector<int>& nums1, int sta, std::vector<int>& nums2, int stb, int kth){// 起始位置超出数组长度，直接返回另外一个数组的位置if (sta >= nums1.size()) return nums2[stb + kth - 1];if (stb >= nums2.size()) return nums1[sta + kth - 1];if (kth == 1) return std::min(nums1[sta], nums2[stb]); // 递归到 k = 1int h = kth / 2;int vala = nums1.size() - sta >= h? nums1[sta + h - 1] : nums1.back();int counta = nums1.size() - sta >= h ? h : nums1.size() - sta;int valb = nums2.size() - stb >= h? nums2[stb + h - 1] : nums2.back();int countb = nums2.size() - stb >= h ? h : nums2.size() - stb;if(vala <= valb){return findKth(nums1, sta + counta, nums2, stb, kth - counta);}return findKth(nums1, sta, nums2, stb + countb, kth - countb);}double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2) {int n = nums1.size();int m = nums2.size();int t = n + m; // 总长度// 无论是奇数还是偶数，中位数都是以下索引（奇数的 id0 和 id1 相同）int id0 = (t + 1) / 2; int id1 = (t + 2) / 2;int val0 = findKth(nums1, 0, nums2, 0, id0); // 寻找第 id0 位对应的数值，第1次左起点从0开始int val1 = findKth(nums1, 0, nums2, 0, id1); // 寻找第 id1 位对应的数值，第1次左起点从0开始return (val0 + val1) / 2.0;}
};int main(int argc, char *argv[]){std::vector<int> nums1 = {1, 2};std::vector<int> nums2 = {3, 4};Solution s1;float middle = s1.findMedianSortedArrays(nums1, nums2);std::cout << "middle is: " << middle << std::endl;
}主要思路：利用归并排序，将两个数组合并为一个有序的数组，最后返回其中位数；
#include <vector>
#include <iostream>class Solution {
public:void Merge_sort(std::vector<int> &nums1, std::vector<int> &nums2, std::vector<int> &nums){int i = 0, j = 0;while(i < nums1.size() && j < nums2.size()){if(nums1[i] <= nums2[j]){nums.push_back(nums1[i]);i++;}else{nums.push_back(nums2[j]);j++;}}if(i >= nums1.size()){while(j < nums2.size()){nums.push_back(nums2[j]);j++;}}if(j >= nums2.size()){while(i < nums1.size()){nums.push_back(nums1[i]);i++;}}}double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2) {int n = nums1.size();int m = nums2.size();int l = n + m;Merge_sort(nums1, nums2, nums);int v0 = nums[(l+1) / 2 - 1];int v1 = nums[(l+2) / 2 - 1];return (v0+v1) / 2.0;}private:std::vector<int> nums;
};int main(int argc, char *argv[]){std::vector<int> nums1 = {1, 2};std::vector<int> nums2 = {3, 4};Solution s1;float middle = s1.findMedianSortedArrays(nums1, nums2);std::cout << "middle is: " << middle << std::endl;
}5--最长回文子串
主要思路：
遍历字符串的每个字符，用两个指针 l 和 r 分别指向其左字符和右字符，判断左字符和右字符是否相等，不断贪心向外扩展；
需要注意区分奇数回文子串和偶数回文子串，奇数回文子串首次传入的左指针和右指针相同，都指向当前字符；
#include <string>
#include <iostream>class Solution {
public:void search(int l, int r, std::string s){int len = s.length();while(l >= 0 && r < len && s[l] == s[r]){l--;r++;}if((r - l - 1) > max){max = r - l - 1;start = l + 1;} }std::string longestPalindrome(std::string s) {for(int i = 0; i < s.length(); i++){search(i, i, s);// 奇数回文子串search(i, i+1, s); // 偶数回文子串}return s.substr(start, max);}
private:int max = 1;int start = 0;
};int main(int argc, char *argv[]){std::string s = "cbbd";Solution s1;std::string ret = s1.longestPalindrome(s);std::cout << ret << std::endl;
}
