LeetCode刷题数组&双指针经典例题-创新互联

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 的关系

1. 因为是划分数组，在对两数组大小和为偶数时划分和奇数是划分时情况是不同的，为偶数时， i 和 j 的和直接为俩数组的大小的一半
2. 为奇数时，因为人为规定划分后的两块数组左边的数组元素要多于右边的数组元素(多一个)，所以i 和 j 的和应该为俩数组的大小 + 1 的一半

因为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）在讨论完数组划分的规则，就要考虑对特殊情况的处理

1. i == 0时，nums1数组的值都较大，所以左界数组的max为nums2[j-1];
2. 如果j == 0，nums2数组的值都较大，所以左界数组的max为nums1[i-1];
3. i == m时，右界数组的min就为nums2[j];
4. j == n时，右界数组的min就为nums1[i];
   

（4）看到这里突然想到一个问题，划分后怎么算才能得到中位数？

1. 答：左边大和右边最小的和除以二，不过这是在偶数情况下，
2. 如果在奇数情况下呢，直接返回左边数组的大值即可。

下面是具体代码实现 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；

1. 在 m + n 为偶数时，中位数为两个数组合并后的第(m + n) / 2和第(m + n) / 2 + 1个元素的平均值
2. 在 m + n 为奇数时，中位数为两个数组合并后的第 (m + n) / 2个元素

那么问题是不是可以转换为求第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]的对比，分为三种情况，

1. 如果 A[k/2−1]
2. 如果 A[k/2−1]>B[k/2−1]，则可以排除B[0] 到B[k/2−1]。
3. 如果 A[k/2−1]=B[k/2−1]，则可以归入第一种情况处理。

比较完常规情况下的A[k/2 - 1]和B[k/2 - 1]的对比，则看一下对特殊情况下的A[k/2 - 1]和B[k/2 - 1]的对比

有以下三种情况需要特殊处理：

1. 如果 A[k/2−1] 或者B[k/2−1] 越界，那么我们可以选取对应数组中的最后一个元素。在这种情况下，我们必须根据排除数的个数减少 k 的值，而不能直接将 k 减去 k/2。
2. 如果一个数组为空，说明该数组中的所有元素都被排除，我们可以直接返回另一个数组中第 k 小的元素。
3. 如果 k=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的更新和两数组的遍历过程不是很好理解，在这里在综上所述。

1. 在对k定义时，因为我们知道在对m + n为奇偶数的情况下，都离不开(m + n) / 2 和 (m + n) / 2 + 1，所以通过k，将两种情况合并，通过传参时的改变(+1)，能得到不同情况下要求的(m + n) / 2 或 (m + n) / 2 + 1。
2. 对于k的更新，因为在对比A[k/2 - 1]和B[k/2 - 1]时出现的较小值，最多只有k/2 - 1个元素比它小，所以我们可以将AB数组的前k/2 - 1个元素都删去，即为k = k - k / 2 + 1。
3. 对于两数组的遍历，即将出现较小值的数组从k/2 - 1向下一个元素继续遍历。

3.三数之和

题意：两数之和的进化版，找到数组中三个不相同的元素，使得它们的和为0.

此题和两数之和的解法类型，但多出了结果不能包含重复的三元组，导致多出了查重的操作。
解法上使用排序和双指针。

为什么解法上不能直接用和两数之和的暴力解法两层for循环相同的三层for循环解决呢？那当然是n^3的时间复杂度可能导致超时，所以排除了暴力解法。
那么如果使用和两数之和解法中的哈希表法呢？由于数过多，可能导致空间复杂度也过高，所以也不考虑哈希表法。
PS：找了找题解，发现代码随想录给出了哈希表的解法，这里直接CV过来，有兴趣的自己琢磨一下

哈希解法
两层for循环就可以确定 a 和b 的数值了，可以使用哈希法来确定 0-(a+b) 是否在 数组里出现过，其实这个思路是正确的，但是我们有一个非常棘手的问题，就是题目中说的不可以包含重复的三元组。

把符合条件的三元组放进vector中，然后再去重，这样是非常费时的，很容易超时，也是这道题目通过率如此之低的根源所在。

去重的过程不好处理，有很多小细节，如果在面试中很难想到位。

时间复杂度可以做到O(n^2)，但还是比较费时的，因为不好做剪枝操作。

大家可以尝试使用哈希法写一写，就知道其困难的程度了。

class Solution {
public:
    vector>threeSum(vector& nums) {
        vector>result;
        sort(nums.begin(), nums.end());
        // 找出a + b + c = 0
        // a = nums[i], b = nums[j], c = -(a + b)
        for (int i = 0; i< nums.size(); i++) {
            // 排序之后如果第一个元素已经大于零，那么不可能凑成三元组
            if (nums[i] >0) {
                break;
            }
            if (i >0 && nums[i] == nums[i - 1]) { //三元组元素a去重
                continue;
            }
            unordered_setset;
            for (int j = i + 1; j< nums.size(); j++) {
                if (j >i + 2
                        && nums[j] == nums[j-1]
                        && nums[j-1] == nums[j-2]) { // 三元组元素b去重
                    continue;
                }
                int c = 0 - (nums[i] + nums[j]);
                if (set.find(c) != set.end()) {
                    result.push_back({nums[i], nums[j], c});
                    set.erase(c);// 三元组元素c去重
                } else {
                    set.insert(nums[j]);
                }
            }
        }
        return result;
    }
};

作者：carlsun-2
链接：https://leetcode.cn/problems/3sum/solution/dai-ma-sui-xiang-lu-dai-ni-gao-ding-ha-x-jzkx/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

那为什么想到使用排序和双指针的解法呢？
下面是具体推导过程：
假设一个数组为 arr[6] = {1, 2, 3, 4, 5, 6}; 该数组为一个有序数组
（抛开题目，只谈暴力解法推导到排序和双指针解法）
假设要求的是和为8
我们可以用暴力解法的思路去推导：如果嵌套三层for循环，

第一层for循环是先拿数组的一个元素

for1 ->1

第二层for循环是拿第一层for循环拿的元素的后一个元素

for2 ->2

第三层for循环是拿第二层for循环拿的元素后的一个元素

for3 ->3

先是第三层for循环开始遍历，拿到后面的 4，5，6，我们是不是可以想到以第三层的遍历工具(假设为k)和最后一个元素6形成了一个窗口，k在窗口内遍历，当前arr[k] = 3,总和(记为target)小于8，则k继续向后遍历，当前arr[k] = 4，target小于8，k继续向后遍历，当前arr[k] = 5，此时target要大于8。通过这个过程，我们能体会到k是不断往大的元素去趋近求和，那为节省时间，能不能让大的元素直接跑过来，即为再增加一个指针(记为right)指向最后一个元素(大的一个元素)，如果当arr[k] + arr[right] >8，则说明right指针指向的元素过大，让right--，过小让k++。

总结一下推导过程：

1. 就是找到要创建一个窗口的思路，窗口左界和右界是什么，在窗口中遍历的工具是什么
2. 体会在for循环中就是不断创建窗口去遍历的过程，但窗口的右界是固定的，不够灵活，可能产生过多的浪费时间的操作，所以我们考虑模拟一个窗口，让遍历工具动和左右界动，减少时间浪费。

但我们发现如果在最后一层or循环中去设置一个right，就有点画蛇添足了(因为在最后一层for循环中只需要k去遍历足够了)，所以我们不妨一共就一层for循环(以i作为遍历工具)，让nums[i]和nums[right]（right = nums.size() - 1）构成一个窗口，在设置一个指针left作为窗口中的遍历工具，如果nums[i] + nums[left] + nums[right] >目标值，则让right--，如果小于目标值，则left++，如果相同，则进行存放操作。

总体思路已经梳理完毕，该思路都是基于数组是有序的，所以对数组排序后操作是必然的，所以综上所述使用排序和双指针法。

下面就是对于排重的操作实现了
（1）对i进行去重：

• 该去重操作要在for循环开始时操作
• 如果nums[i]和nums[i-1]的元素相同，则跳过该元素(continue)，并且i >0。

  if (i >0 && nums[i] == nums[i - 1]) {
      continue;
  }

• 那为什么不用nums[i]和nums[i+1]去判断是否相同呢，因为可能将会漏掉-1,-1,2 这种情况。

（2）对left和right去重：

• 该去重操作要在得到一个三元组后执行，如果在得到一个三元组前执行，则可能导致0，0，0 的情况被错误处理了。
• 具体操作就是对比left后的元素和right前面的元素

  while (right >left && nums[right] == nums[right - 1]) right--;
  while (right >left && nums[left] == nums[left + 1]) left++;
  

下面就是具体实现的总体代码 C++版

class Solution {
public:
    vector>threeSum(vector& nums) {
        vector>ret;
        sort(nums.begin(), nums.end());
        for(int i=0; i0){
                return ret;
            }
            //答案中不可以包含重复的三元组,所以要进行排重操作
            if(i >0 && nums[i] == nums[i-1]){
                continue;
            }
            int left = i + 1;
            int right = nums.size() - 1;
            while(left< right){
                if(nums[i] + nums[left] + nums[right] >0){
                    right--;
                }
                else if(nums[i] + nums[left] + nums[right]< 0){
                    left++;
                }
                else{
                    ret.push_back(vector{nums[i], nums[left], nums[right]});
                    //继续查重
                    while(left< right && nums[left] == nums[left + 1]) left++;
                    while(left< right && nums[right] == nums[right - 1]) right--;
                    //如果无重复元素也要继续遍历
                    left++;
                    right--;
                }
            }
        }
        return ret;
    }
};

懂了三数之和，那四数之和的解法其实也差不多，链接在下面，可以尝试做一下

四数之和

4.颜色分类

题意：在不适用排序函数的情况下，将数组按0,1,2的顺序排列好。

可以直接不讲武德用sort(nums.begin(), nums.end())（bush）
本题可以用单双指针两种解法，不同方法也只是遍历方式不同，本题就不讨论为什么使用单双指针的思路了。

排序0,1,2说白了也就是把0放前头，1放中间，2放后头，那是不是可以用一个指向头的变量(记为pre)，当遍历到0时，就让当前遍历的元素和nums[pre]交换，并让pre++，当退出当前for循环时，pre就指向最后一个0的下一个元素的位置，此时开始遍历1，找到1时就和nums[pre]交换。

下面是代码实现 C++版

class Solution {
public:
    void sortColors(vector& nums) {
        int pre = 0;
        // 第一次遍历找0
        for(int i=0; i

class Solution {
public:
    void sortColors(vector& nums) {
        int p0 = 0, p2 = nums.size() - 1;
        for(int i=0; i<=p2; ++i){
            // 此处为什么不用if而用while呢
            // 防止p2和i所指向的元素都为2，p2拿到不为2的元素塞给nums[i]
            // 例如测试用例[2, 1, 2]通过不了
            while(i<= p2 && nums[i] == 2){
                swap(nums[i], nums[p2]);
                --p2;
            }
            if(nums[i] == 0){
                swap(nums[i], nums[p0]);
                ++p0;
            }
        }
    }
};

class Solution {
public:
    void sortColors(vector& nums) {
        int n = nums.size();
        int p0 = 0, p1 = 0;
        for(int i=0; i

for(int i=0; i

class Solution {
public:
    string minWindow(string s, string t) {
        //定义两个哈希表存放s字符串和t字符串中元素出现的次数
        unordered_maphs, ht;
        //将t中的信息录入哈希表ht中
        for(int i=0; iht[s[j]]) hs[s[j++]]--;
            //如果有效字符数等于t的字符串长度，则说明遍历完了
            if(cnt == t.length()) {
                //如果ans为空 or ans的长度要大于窗口的长度，则将ans字符串存放内容初始一下
                if(ans.empty() || ans.length() >i - j + 1) {
                    //substr函数：s.substr(pos, len) 包含s中从pos开始的len个字符的拷贝
                    ans = s.substr(j, i - j + 1);
                }
            }
        }
        return ans;
    }
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        //创建一个哈希表visited
        unordered_setvisited;
        //用head作为遍历工具
        while(head != nullptr) {
            //如果重复出现过(即为count函数返回的不是0)，则直接return此时的节点即可
            if(visited.count(head)) {
                return head;
            }
            //反正则将当前节点存放在哈希表中
            visited.insert(head);
            //继续向后遍历
            head = head->next;
        }
        return nullptr;
    }
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        while(fast != NULL && fast->next != NULL){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow){
                ListNode *index1 = head;
                ListNode *index2 = slow;
                while(index1 != index2){
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index2;
            }
        }
        return NULL;
    }
};

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vectorvals;
        while (head != nullptr) {
            vals.emplace_back(head->val);
            head = head->next;
        }
        for (int i = 0, j = (int)vals.size() - 1; i< j; ++i, --j) {
            if (vals[i] != vals[j]) {
                return false;
            }
        }
        return true;
    }
};

class Solution {
    ListNode *frontPointer;
public:
    bool recursivelyCheck(ListNode* currentNode){
        // 让currentNode从链表的尾节点开始操作
        if(currentNode != nullptr){
            if(!recursivelyCheck(currentNode->next)){
                return false;
            }
            if(currentNode->val != frontPointer->val){
                return false;
            }
            // 让frontPointer从链表头开始遍历
            frontPointer = frontPointer->next;
        }
        return true;
    }

    bool isPalindrome(ListNode* head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }
};

class Solution {
public:
    void moveZeroes(vector& nums) {
        int left = 0, right = 0;
        while(right< nums.size()){
            //左指针的零与右指针的非零数交换，使得非0元素相对顺序不被改变
            if(nums[right]){
                swap(nums[left], nums[right]);
                left++;
            }
            right++;
        }
    }
};