LCR006-LCR009双指针问题

剑指offer（专项突破版）2.2 双指针

题目链接：LCR006-排序数组中的两个数字之和

分析：用两个指针P1和P2分别指向数组中的两个数字。指针P1初始化指向数组的第1个（下标为0）数字，指针P2初始化指向数组的最后一个数字。如果指针P1和P2指向的两个数字之和等于输入的k，那么就找到了符合条件的两个数字。如果指针P1和P2指向的两个数字之和小于k，那么我们希望两个数字的和再大一点。由于数组已经排好序，因此可以考虑把指针P1向右移动。因为在排序数组中右边的数字要大一些，所以两个数字的和也要大一些，这样就有可能等于输入的数字k。同样，当两个数字的和大于输入的数字k时，可以把指针P2向左移动，因为在排序数组中左边的数字要小一些。

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        // 定义两个指针，一个从前往后开始扫描，一个从后往前开始扫描
        int i = 0;
        int j = numbers.size() - 1;
        while(1){
            int sum = numbers[i] + numbers[j];
            if(sum == target){
                break;
            }
            else if(sum < target){
                i++;
            }
            else{
                j--;
            }
        }
        vector<int> res;
        res.push_back(i);
        res.push_back(j);
        return res;
    }
};

时间复杂度分析： 时间复杂度是O（n）、空间复杂度是O（1）。

结果：

题目链接：LCR007-三数之和

分析：先对数组进行排序。在固定用变量i指向的数字之后，找出所有下标大于i并且和为-nums[i]的两个数字（下标分别为j和k）。如果nums[i]、nums[j]、nums[k]的和大于0，那么下标k向左移动；如果nums[i]、nums[j]、nums[k]的和小于0，那么下标j向右移动。如果3个数字之和正好等于0，那么向右移动下标j，以便找到其他和为-nums[i]的两个数字。由于要避免重复的三元组，因此使用while循环让下标i、j、k跳过重复的数字。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        // 排序
        sort(nums.begin(),nums.end());
        // 结果
        vector<vector<int>> res;
        //固定一个元素
        for(int i = 0;i < n-2;i++){
            int j = i + 1;
            int k = n - 1;
            while(j < k){
                int sum = nums[i] + nums[j] + nums[k];
                if(sum == 0){
                    res.push_back({nums[i],nums[j],nums[k]});
                    //去掉重复元素
                    while(j<k && nums[j]==nums[j+1]) j++;
                    while(j<k && nums[k]==nums[k-1]) k--;
                    j++;
                    k--;
                }
                else if(sum < 0){
                    j++;
                }
                else{
                    k--;
                }
            }
            //跳过重复元素
            while(i<n-2 && nums[i]==nums[i+1]) i++;         
        }
        return res;
    }
};

时间复杂度分析： 用O（n）时间在排序数组中找出和为给定值的两个数字的方法，由于需要固定数组中的每个数字，因此查找三元组的时间复杂度是O（n2）。排序算法的时间复杂度通常是O（nlogn），因此这种解法的总的时间复杂度是O（nlogn）+O（n2），仍然是O（n2）。

结果：

题目链接：LCR008-长度最小的子数组

分析：初始时两个指针p1、p2同时指向首个元素，两个指针之间的元素和小于target，p2向右移动一位；和大于等于target，p1向右移动一位，同时更新最短数组长度。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int res = INT_MAX;
        // 定义双指针
        int i = 0;
        int j = 0;
        // 遍历
        int sum = 0;
        for(; j < nums.size();j++){
            sum += nums[j];
            while(i <= j && sum >= target){
                res = min(res,j-i+1);
                sum -= nums[i];
                i++;
            }
        }
        if(res == INT_MAX){
            res = 0;
        }
        return res;
    }
};

时间复杂度分析： 假设数组的长度为n，尽管上述代码中有两个嵌套的循环，该解法的时间复杂度仍然是O（n）。这是因为在这两个循环中，变量left和right都是只增加不减少，变量right从0增加到n-1，变量left从0最多增加到n-1，因此总的执行次数是O（n）。

结果：

题目链接：LCR00-乘积小于k的子数组

分析：
用指针P1和P2指向数组中的两个数字，两个指针之间的数字组成一个子数组。指针P1永远不会走到指针P2的右边。两个指针初始化都指向数组的第1个数字（下标为0的数字）。

如果两个指针之间的子数组中数字的乘积小于k，则向右移动指针P2。向右移动指针P2相当于在子数组中添加一个新的数字，由于数组中的数字都是正整数，因此子数组中数字的乘积就会变大。

如果两个指针之间的子数组中数字的乘积大于或等于k，则向右移动指针P1。向右移动指针P1相当于从子数组中删除最左边的数字，由于数组中的数字都是正整数，因此子数组中数字的乘积就会变小。

由于我们的目标是求出所有数字乘积小于k的子数组的个数，一旦向右移动指针P1到某个位置时子数组的乘积小于k，就不需要再向右移动指针P1。这是因为只要保持指针P2不动，向右移动指针P1形成的所有子数组的数字乘积就一定小于k。此时两个指针之间有多少个数字，就找到了多少个数字乘积小于k的子数组。

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int res = 0;
        int product = 1;
        int i = 0;
        int j = 0;
        // 双指针
        int len = nums.size();
        for(;j < len;j++){
            product *= nums[j];
            while(i <= j && product >= k){
                product /= nums[i++];
            }
            res += j>=i ? j-i+1 : 0;
        }
        return res;
    }
};

时间复杂度分析： 和第八题一样，假设数组的长度为n，尽管上述代码中有两个嵌套的循环，该解法的时间复杂度仍然是O（n）。这是因为在这两个循环中，变量i和j都是只增加不减少，变量j从0增加到n-1，变量i从0最多增加到n-1，因此总的执行次数是O（n）。

结果：

总结

全局遍历： 当需要对整个数组进行遍历操作时，例如计算数组中元素的总和、查找特定元素等，可以将两个指针同时指向数组起始位置，并依次向后移动，直到遍历完整个数组。

寻找目标： 在一些需要从头开始寻找某个目标的情况下，可以将一个指针指向数组的起始位置，另一个指针指向数组的末尾位置，然后根据目标的条件逐步缩小指针所代表的区间，最终找到目标或者达到特定的结束条件。