扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
1.两数之和
题意：在数组中找两个数，该两个数的和为target，返回下标。
江湖上总流传的一句：有人相爱，有人夜里看海，有人LeetCode第一题做不出来。作为小白的我，第一眼看这题也是懵逼的，于是打开题解，看到了这一句经典的话。
当然，这题在题解的帮助下其实并不难，最简单的方法就是暴力求解了，用两层for循环去遍历一下数组即可，如果满足条件存放进新的数组即可，下面是暴力求解的代码 C++版本
class Solution {
public:
vectortwoSum(vector& nums, int target) {
for(int i=0; iret(2);
ret[0] = i;
ret[1] = j;
return ret;
}
}
}
return {};
}
}; 当然，这题只用单纯的暴力求解就太low了，如果要求n数之和，那时间复杂度不得大上天，所以我们要去优化一下解法。
这题优化解法就使用哈希表，那么我们来思考一下为什么要使用哈希表？
我们的目的是在数组中快速的找到目标值位置，注意关键字“值” “位置”，而哈希表就是一种位置和值的关系，所以可以想到使用哈希表的方法。
那么如何用哈希表解决该题呢？
假设target = nums[a] + nums[i];
target - nums[i] = b;
b没有在哈希表中的键中出现过，则将key = nums[i] value = i;
target - nums[a] = c;
如果b == nums[a] and c == nums[i](c在key中出现过)
则直接可得到target = nums[a] + nums[i];通过这个推导，我们就知道了大体思路，如果 target - nums[i] 的结果在哈希表的键中没有出现过，则将key = nums[i]，value = i，如果target - nums[i] 的结果在哈希表的键中出现过，则将下标i和以结果为键的值return出来。
下面为具体代码实现 C++
class Solution {
public:
vectortwoSum(vector& nums, int target) {
//创建一个哈希表hashtable
unordered_maphashtable;
//遍历数组nums
for(int i=0; isecond, i};
}
//将nums[i]作为键，i作为值存放到哈希表中
hashtable[nums[i]] = i;
}
//如果都不满足，则return 空
return {};
}
}; 时间复杂度通过哈希表的过渡，从O(N^2)降低到O(N)，空间复杂度由O(1)也上升为O(N)，典型的空间换时间策略。
2.寻找两个正序数组的中位数
题意：给定两个数组，找到两个数组的中位数，并返回。
此题也可以直接用暴力解法找两个数组的中位数，可以直接合并为一个数组，对一个数组找中位数。下面是暴力解法的代码实现 C++
class Solution {
public:
double findMedianSortedArrays(vector& nums1, vector& nums2) {
int m = nums1.size() - 1;
int n = nums2.size() - 1;
int i = m + n + 1;
vectornvec(m + n + 2, 0);
// 合并数组到nvec中存放
while (i >= 0) {
if (m >= 0 && n >= 0)
{
if (m >= 0 && nums1[m] >= nums2[n])
{
nvec[i--] = nums1[m--];
}
else if (n >= 0 && nums1[m]< nums2[n])
{
nvec[i--] = nums2[n--];
}
}
else
{
if (m< 0)
{
nvec[i--] = nums2[n--];
}
else if (n< 0)
{
nvec[i--] = nums1[m--];
}
}
}
// 如果两个数组相加长度为偶数，则直接找到nvec数组的一半的左右两个数，相加除二即可
if (((nums1.size() + nums2.size()) % 2) == 0)
{
double res = (double(nvec[(nums1.size() + nums2.size()) / 2 - 1]) +
double(nvec[(nums1.size() + nums2.size()) / 2])) / 2.0;
return res;
}
// 如果相加为奇数，则直接return nvec数组的中间元素即可
else
{
return nvec[(nums1.size() + nums2.size()) / 2];
}
}
}; 这个方法就不思考为什么了，看了原理就知道了，本质是个算法。
此图来自B站up主(找不到这个up主了，如果有知道的告诉一声)
此题主要是如何划分的问题和划分时边界问题的处理，使用 i 和 j 划分两个数组。
（1）先讨论一下 i 和 j 的关系
因为int类型下是向下取整的(可以直接省略0.5)，所以可以将奇数偶数的情况合并，
i + j = (nums1.size() + nums2.size() + 1) / 2
（2）讨论完 i 和 j 的关系，我们就该讨论如何划分数组了(数组划分有什么规则)
在分界时，要遵循两数组(分为上下俩数组，上数组长度为m，下数组长度为n)分界后，
nums1[i-1]< nums2[j](左上<右下)
nums2[j-1]< nums1[i](左下<右上)
（3）在讨论完数组划分的规则，就要考虑对特殊情况的处理
（4）看到这里突然想到一个问题，划分后怎么算才能得到中位数？
下面是具体代码实现 C语言(和C++只是交换数组元素大小时不同)
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
//保证m<= n
if (nums1Size >nums2Size) {
int* temp = nums1;
nums1 = nums2;
nums2 = temp;
int tempNum = nums1Size;
nums1Size = nums2Size;
nums2Size = tempNum;
}
int m = nums1Size;
int n = nums2Size;
//用IMin和IMAX去帮助确定i
int iMin = 0, iMax = m;
while(iMin<= iMax){
int i = (iMin + iMax) / 2;
// i + j = 分界后的左边元素的总和 = (m + n + 1) / 2
// 因为i和j就是将两个数组平均分为两部分了，偶数情况下i + j直接等于(m + n) / 2，
// 奇数情况下i + j = (m + n + 1) / 2,
// 因为默认规定总元素数为奇数时左界数组的元素要比右界元素多1，
// 但在int下不取小数，所以和偶数情况合并
int j = (m + n + 1) / 2 - i;
//如何定义好i的区间
//在分界时，要遵循两数组(分为上下俩数组，上数组长度为m，下数组长度为n)分界后，
// nums1[i-1]< nums2[j](左上<右下)
// nums2[j-1]< nums1[i](左下<右上)
//如果nums2[j - 1] >nums1[i](左下>右上) 让i右移，变大(俩数组升序排列)
if(j != 0 && i != m && nums2[j-1] >nums1[i]){
iMin = i + 1;
}
//如果nums1[i-1] >nums2[j](左上>右下) 让i左移，变小
else if(i != 0 && j< n && nums1[i-1] >nums2[j]){
iMax = i - 1;
}
else{
//存放左界数组的max
int maxLeft = 0;
//i == 0时，nums1数组的值都较大，所以左界数组的max为nums2[j-1];
if(i == 0){
maxLeft = nums2[j-1];
}
//如果j == 0，nums2数组的值都较大，所以左界数组的max为nums1[i-1];
else if(j == 0){
maxLeft = nums1[i-1];
}
//ij都不为0时，直接找nums1[i-1]和nums2[j-1]的大值即可
else{
maxLeft = fmax(nums1[i-1], nums2[j-1]);
}
//如果总数组元素为奇数，直接返回左界数组的max即可
if((m + n) % 2 == 1){
return maxLeft;
}
//如果总数组元素为奇数时
//存放右界数组的min
int minRight = 0;
//i == m时，右界数组的min就为nums2[j];
if(i == m){
minRight = nums2[j];
}
//j == n时，右界数组的min就为nums1[i];
else if(j == n){
minRight = nums1[i];
}
//i不等于m且j不等于n时，直接找nums1[i]和nums2[j]的最小值即可
else{
minRight = fmin(nums2[j], nums1[i]);
}
//为偶数的情况下返回左界数组的max和右界数组的min的和除以2.0
// (因为题目要返回的是double类型)
return (maxLeft + minRight) / 2.0;
}
}
//如果都不满足，返回0.0(double类型)
return 0.0;
}对于两个数组大小相加为奇数or偶数时，求得的中位数由划分数组的方法也能了解到有所不同
nums1.size() == m nums2.size() == n；
那么问题是不是可以转换为求第k个小的数，其中k为 (m + n) / 2 或者 (m + n) / 2 + 1;
那如何找到第k个小的数呢？
假设两个数组为数组A和数组B，求得第k个小的数可以通过比较A[k/2 - 1]和B[k/2 - 1]，在k/2 - 1前有k/2 - 1个元素，对于A[k/2 - 1]和B[k/2 - 1]中的较小值，最多只有可能有 k/2 - 1 + k/2 - 1<= k - 2个元素比它小，所以当前的较小值不可能为第k个数。
对A[k/2 - 1]和B[k/2 - 1]的对比，分为三种情况，
比较完常规情况下的A[k/2 - 1]和B[k/2 - 1]的对比，则看一下对特殊情况下的A[k/2 - 1]和B[k/2 - 1]的对比
有以下三种情况需要特殊处理：
下面是二分查找具体代码的实现 C++
class Solution {
public:
int getKthElement(const vector& nums1, const vector& nums2, int k) {
// k是由将两个数组合并后得到的要求的中位数的元素的下标
int m = nums1.size();
int n = nums2.size();
// 创建两个遍历工具
int index1 = 0, index2 = 0;
while (true) {
// 边界情况
// 处理本质其实和划分数组解法也差不多，只不过减少了对于index1和index2为0的情况
if (index1 == m) {
return nums2[index2 + k - 1];
}
if (index2 == n) {
return nums1[index1 + k - 1];
}
if (k == 1) {
return min(nums1[index1], nums2[index2]);
}
// 正常情况
// 取min是防止越界的情况出现
int newIndex1 = min(index1 + k / 2 - 1, m - 1);
int newIndex2 = min(index2 + k / 2 - 1, n - 1);
// 用pivot1和pivot2作为对比的工具
int pivot1 = nums1[newIndex1];
int pivot2 = nums2[newIndex2];
// 如果是A数组中出现较小值
if (pivot1<= pivot2) {
// k值更新 k = k - k/2 + 1，去掉AB数组前面的k/2 - 1个元素
k -= newIndex1 - index1 + 1;
// 让出现较小值的数组继续向k/2 - 1的下一个元素去遍历，即为
// index1 = newIndex(k/2 - 1) + 1；
index1 = newIndex1 + 1;
}
// 如果是B数组中出现较小值
else {
k -= newIndex2 - index2 + 1;
index2 = newIndex2 + 1;
}
}
}
double findMedianSortedArrays(vector& nums1, vector& nums2) {
int totalLength = nums1.size() + nums2.size();
// 如果 m + n 为奇数时，则找到两个有序数组的第m + n / 2 个元素
if (totalLength % 2 == 1) {
return getKthElement(nums1, nums2, (totalLength + 1) / 2);
}
// 反之则找到两个有序数组的第(m + n) / 2 和第(m + n) / 2 + 1的平均值
else {
return (getKthElement(nums1, nums2, totalLength / 2) +
getKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0;
}
}
}; 本菜鸡看该题解时，就感觉k的定义、k的更新和两数组的遍历过程不是很好理解，在这里在综上所述。
3.三数之和
题意：两数之和的进化版，找到数组中三个不相同的元素，使得它们的和为0.
此题和两数之和的解法类型，但多出了结果不能包含重复的三元组，导致多出了查重的操作。
解法上使用排序和双指针。
为什么解法上不能直接用和两数之和的暴力解法两层for循环相同的三层for循环解决呢？那当然是n^3的时间复杂度可能导致超时，所以排除了暴力解法。
那么如果使用和两数之和解法中的哈希表法呢？由于数过多，可能导致空间复杂度也过高，所以也不考虑哈希表法。
PS：找了找题解，发现代码随想录给出了哈希表的解法，这里直接CV过来，有兴趣的自己琢磨一下