<1>两数之和
原题链接：两数之和 – 力扣（LeetCode）
思路
我们的目的是在数组中找到两个数a和b，使得a+b=target，且数组中只会存在一组a、b满足条件。
因为target已知，我们在遍历数组时可以得到数a，那么根据b=target-a，我们实际上可以在得到a的同时，得到所需要的b值，那么判断b是否已经出现即可。
那么，问题就转化为了如何在得到a的时候，查看我们是否已经遍历过b。
一个简单的思路就是我们将每次遍历得到的元素存起来，每次遍历时，我们判断其对应的数是否已经存储过，如果我们已经存储过a，那么我们返回当前下标和a的下标即可。
代码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
//使用unordered_map，其底层实现是哈希表，有良好的查找性能
//第一个位置的int存储b，第二个位置的int存储下标
unordered_map<int,int> hash;
vector<int> result;//result用于存储最终结果
for(int i = 0;i < nums.size();++i)
{
int b = target - nums[i];//得到b的值
if(hash.find(b) != hash.end())//判断b是否已经遍历过
{
//遍历过则输出结果
result.push_back(hash[b]);//b的下标
result.push_back(i);//当前下标
return result;
}
hash[nums[i]] = i;//没有遍历过则将当前下标存储在unordered_map中
}
return result;
}
};
<2>两数相加
原题链接：两数相加
思路
我们的目的是将两个链表的数字相加得到结果链表。
我们可以同步遍历两个链表，将每一位的数字相加，需要注意的是进位信息。
当一个链表结束时，我们要判断另一个链表是否也结束，如果没有，则需要继续进行，这里需要特别注意进位信息是有可能传递到高位的。
代码
/**
* 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* l3 = new ListNode(0,nullptr);//先生成结果链表的第一个节点
int flag = 0,first = 1;//flag表示是否存在进位，first表示是否是第一位的运算
ListNode* p = l3;//使用p代替l3参与遍历，这样我们返回l3即可
while(l1 != nullptr && l2 != nullptr)//当两个链表都不为空时，遍历每一位
{
int sum = l1->val + l2->val + flag;//这一位的结果是两个链表的和再加上进位
if(sum >= 10)
{
sum = sum
flag = 1;//产生进位
}
else
{
flag = 0;//不产生进位
}
if(first == 1)//因为我们提前new了一个节点，所以第一位运算无需new新节点
{
p->val = sum;
p->next = nullptr;
first = 0;
}
else//不是第一位运算，我们就正常按照链表的尾插进行
{
ListNode* q = new ListNode(sum,nullptr);
p->next = q;
p = q;
}
l1 = l1->next;
l2 = l2->next;
}
while(l1 != nullptr)//当l2为空但l1不为空时
{
//与上面的逻辑一样，只是将l2的节点视为0
int sum = l1->val + flag;
if(sum >= 10)
{
sum = sum
flag = 1;
}
else
{
flag = 0;
}
//因为题目假设没有空链表，所以进入此处时一定不是第一位运算
ListNode* q = new ListNode(sum,nullptr);
p->next = q;
p = q;
l1 = l1->next;
}
while(l2 != nullptr)//当l1为空但l2不为空时
{
//与上方同理
int sum = l2->val + flag;
if(sum >= 10)
{
sum = sum
flag = 1;
}
else
{
flag = 0;
}
ListNode* q = new ListNode(sum,nullptr);
p->next = q;
p = q;
l2 = l2->next;
}
if(flag == 1)//如果最高位运算之后，扔存在进位信息，结果需要再进一位
{
ListNode* q = new ListNode(1,nullptr);
p->next = q;
}
return l3;
}
};
<3>无重复字符串的最长子串
原题链接：无重复字符的最长子串
思路
我们的目的是找到字符串中的无重复的最长子串。
那么，我们只需要遍历字符串，当出现重复的字符时，之前已经遍历的字符就形成一个无重复字符的子串。
我们将新的重复的字符添加进子串中，同时需要丢弃子串中已有的重复字符之前的所有字符，同时更新长度信息。
我们比较每次得到的无重复字符串的长度，找到最长的即可。
代码
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char,int> dic;//char存储字符，int存储其所在的位置下标，整体为哈希实现查找效率高
//length记录无重复字符的长度
//max_length记录当前所有无重复字符的最长长度
//head记录当前子串的起始位置
int length = 0,max_length = 0,head = 0;
for(int i = 0;i < s.size();++i)
{
auto it = dic.find(s[i]);//判断当前字符是否出现过，也就是是否重复
if(it == dic.end())//没有出现过
{
dic[s[i]] = i;//存储字符与下标
++length;//增加长度
}
else//出现过
{
if(it -> second < head)//出现过，但不在当前子串的范围内，视为没有重复
{
dic[s[i]] = i;
++length;
}
else//出现过，且在当前子串内重复
{
head = it->second + 1;//更新子串的起始位置为之前重复字符的下一位
length = i - head + 1;//添加新的字符，并更新长度
dic[s[i]] = i;
}
}
if(length > max_length)//每次判断是否需要更新最长长度
{
max_length = length;
}
}
return max_length;
}
};
<4>寻找两个正序数组的中位数
原题链接：寻找两个正序数组的中位数
思路
我们的目的是找到两个正序数组的中位数，中位数的特点是左右两侧的元素个数是相同的。
我们的目的就转换为将数组分割为两个部分，满足以下条件：
- 1.左侧部分和右侧部分的元素个数是相同的
- 2.左侧部分的所有元素都小于右侧部分的所有元素
我们暂且假设两个数组的元素个数都是偶数个，那么我们能够在两个数组中各自找到一个分割线，我们记为数组一的分割线s1和数组二的分割线s2：
- s1的左侧加上s2的左侧，构成了左侧部分
- s1的右侧加上s2的右侧，构成了右侧部分
接下来我们想办法满足上面的两个条件：
- 条件一：元素个数相同的条件是比较好满足的，我们只需要分别取两个数组的中间位置作为分割线即可
- 条件二：我们需要满足左侧小于右侧的条件，最终我们希望得到的是s1的左侧都是左侧部分的元素，s2的右侧都是右侧部分的元素
那么，我们可以通过移动分割线的方式来满足条件二，注意我们需要同时移动两个分割线来保证满足条件一。我们可以通过判断分割线左右两侧的元素来确定分割线的移动方向，我们将s1左侧的元素记为l1，右侧的元素记为r1，s2左侧的元素记为l2，右侧的元素记为r2：
- 当l1>r2时，说明l1理应属于整体右侧部分，但目前属于左侧；相对地，r2理应属于整体左侧部分，但目前属于右侧。此时，我们就左移s1，右移s2，达到交换l1和r2的目的
- 当l2>r1时，说明l2理应属于整体右侧部分，但目前属于左侧；相对地，r1理应属于整体左侧部分，但目前属于右侧。此时，我们就右移s1，左移s2，达到交换l2和r1的目的
- 由于两个数组是有序的，存在前置条件l1<r1，l2<r2，简单推理可知，以上两种情况同时只能有一种成立
当两种情况都不成立时，说明左侧所有元素小于右侧所有元素，满足了条件二。此时，我们取左侧的最大值和右侧的最小值，即可算出中位数。
以上是两种数组元素个数都是偶数的情况，那么对于元素个数为奇数时，我们实际上可以将数组中每个元素重复一次，达到两个数组的元素都是偶数的情况：
- 例如：[1,2,3]，重复为[1,1,2,2,3,3]
- 我们以重复之后的数组为分割用的数组，分割线的位置就是原数组的长度，也就是3，此时分割线在重复后数组下标为3的元素的左侧
- 我们可以得到，分割线左侧元素在原数组的下标为$(3-1)/2$，右侧元素在原数组的下标为$3/2$
- 那么，基于上面的下标规律，我们就可以在实际存储中不存储重复数组，仅在逻辑上使用它
接下来，我们考虑边界情况：
- 当s1到达数组一的最左侧时，我们将s1左侧设为int类型的最小值；到达最右侧时，我们将s1右侧设为int类型的最大值
- 当s2到达数组一的最左侧时，我们将s2左侧设为int类型的最小值；到达最右侧时，我们将s2右侧设为int类型的最大值
当任一数组达到边界情况时，说明整个数组被分到了一侧，我们以数组一达到边界情况为例，数组二同理：
- s1在最左侧，此时l1=INT_MIN，一定存在l1<r2；因为是s1的左移，满足左移的情况是l1>r2，因为发生移动时两种情况不同时成立，一定存在l2<r1。此时，l1<r2且l2<r1，两种情况均不成立，直接得到中位数结果
- 若在此情况下s2在最右侧，此时r2=INT_MAX，同样满足条件；此情况下，s2不可能在最左侧
- s1在最右侧，此时r1=INT_MAX，一定存在l2<r1；因为是s1的右移，满足右移的情况是l2>r1，因为发生移动时两种情况不同时成立，一定存在l1<r2。此时，l1<r2且l2<r1，两种情况均不成立，直接得到中位数结果
- 若在此情况下s2在最左侧，此时r2=INT_MIN，同样满足条件；此情况下，s2不可能在最右侧
代码
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(),n = nums2.size();//得到两个数组的长度
int n1_s = m,n2_s = n;//先分别取两个数组的中间进行划分，分割线为n1_s，n2_s
int n1_l,n1_r,n2_l,n2_r;//分别表示n1_s左侧和右侧，n2_S左侧和右侧的数值
double mid = 0;//存储最终结果的变量
while(true)
{
if(n1_s == 0)//n1_s在最左侧的情况
{
n1_l = INT_MIN;
}
else
{
n1_l = nums1[(n1_s - 1) / 2];
}
if(n1_s == 2 * m)//n1_s在最右侧的情况
{
n1_r = INT_MAX;
}
else
{
n1_r = nums1[n1_s / 2];
}
if(n2_s == 0)//n2_s在最左侧的情况
{
n2_l = INT_MIN;
}
else
{
n2_l = nums2[(n2_s - 1) / 2];
}
if(n2_s == 2 * n)//n2_s在最右侧的情况
{
n2_r = INT_MAX;
}
else
{
n2_r = nums2[n2_s / 2];
}
if(n1_l > n2_r)//满足情况一：进行n1_s的左移和n2_s的右移
{
if(n1_s != 0 && n1_s != 2 * m)
{
--n1_s;
}
if(n2_s != 0 && n2_s != 2 * n)
{
++n2_s;
}
}
else if(n2_l > n1_r)//满足情况二：进行n1_s的右移和n2_s的左移
{
if(n1_s != 0 && n1_s != 2 * m)
{
++n1_s;
}
if(n2_s != 0 && n2_s != 2 * n)
{
--n2_s;
}
}
else if(n1_l <= n2_r && n2_l <= n1_r)//不满足移动条件，说明得到结果
{
double left = 0,right = 0;
if(n1_l < n2_l)//取左侧最大值
{
left = n2_l;
}
else
{
left = n1_l;
}
if(n1_r < n2_r)//取右侧最小值
{
right = n1_r;
}
else
{
right = n2_r;
}
mid = (left + right) / 2;
return mid;
}
}
}
};