【C++】优选算法必修篇之双指针实战：最大连续1的个数 & 将x减到0的最小操作数

我不是呆头

发布于 2025-12-20 14:34:43

170

应用场景

应用场景链接直达请点击<----------

1. 最大连续1的个数

1.1 题目链接

题目链接直达请点击<----------

1.2 题目描述

1.3 题目示例

1.4 算法思路

这道题我们可以通过更新窗口类为1个数的大小并比较来求解，定义一个left和right指针指向第一个数据，并都初始化为0，定义一个count来记录右指针“探险”时遇到的0的个数。

右指针向右探寻，遇到0count++，并更新len（长度）当count>k的时候，就需要进行出窗口，将left++直到left指向的数据为0，执行count--,让count<=k后继续更新结果，直到right走到最后一个数据停止循环。

1.5 核心代码

//最大连续1的个数 & 将x减到0的最小操作数
class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int left = 0, ret = 0, count = 0;
        for (int right = 0; right < nums.size(); right++)
        {
            if (nums[right] == 0) count++;
            while (count > k)
            {
                if (nums[left++] == 0) count--;//=0的时候count--后left会++到下一个位置
            }
            ret = max(ret, right - left + 1);
        }
        return ret;
    }

};

1.6 示例测试（总代码）

//最大连续1的个数 & 将x减到0的最小操作数
#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int left = 0, ret = 0, count = 0;
        for (int right = 0; right < nums.size(); right++)
        {
            if (nums[right] == 0) count++;
            while (count > k)
            {
                if (nums[left++] == 0) count--;//=0的时候count--后left会++到下一个位置
            }
            ret = max(ret, right - left + 1);
        }
        return ret;
    }

};


int main()
{
    int k1 = 2;
    vector<int> nums1 = { 1,1,1,0,0,0,1,1,1,1,0 };
    int result = Solution().longestOnes(nums1, k1);
    cout << result << endl;

    return 0;
}

2. 将x减到0的最小操作数

2.1 题目链接

题目链接直达请点击<----------

2.2 题目描述

2.3 题目示例

2.4 算法思路

根据题目的要求我们可以转换成找到前缀和后缀，让他们的和等于x.
但是我们每次移除一个元素都有两种选择，从最左边移出或者从最右边移除【相当于要枚举所有可能的 (前缀长度, 后缀长度) 组合，使得前缀和 + 后缀和 = x。】
所以我们可以使用反向思维，我们明白移出两端的和需要等于x，所以中间剩下的连续子数组和的就是整个数组的和sum减去x

此时问题可以转化为：找在数组中找到最长的连续子数组，其和等于 sum - x,这样，两端的元素个数（操作次数） = n（数组长度） - 子数组长度，我们要让这个值最小，也就是让中间子数组的长度最大

第一步：计算sum

第二步：计算子数组和的目标值traget = sum-x如果目标值小于0，直接返回-1（说明数组的总和小于x）

第三步：使用滑动窗口找出和为 target 的最长子数组长度 max_len

初始化一个tmp作为右指针探寻时的和，当tmp大于traget说明右指针的数据过大，需要出窗口即左指针右移直到tmp<traget，如果遇到tmp==traget就更新长度的结果，最后返回最大值。

第四步：反向求最小操作数，traget最大的时候，操作数最小。

2.5 核心代码

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = 0;
        for( int a:nums) sum+=a;
        int traget = sum - x, left = 0, right = 0, tmp = 0, ret = -1;
        if(traget < 0) return -1;//小细节

        for(right = 0; right < nums.size(); right++)
        {
            tmp += nums[right];//进窗口
            while(tmp > traget)//判断
                tmp -= nums[left++];//出窗口
            if(tmp == traget)
                ret = max(ret , right - left + 1);//更新结果
        }
        if(ret == -1) return -1;//找不到返回-1
        else return nums.size() - ret;//反向求，traget最大时操作数最小
    }
};

2.6 示例测试（总代码）

#include<iostream>
#include<vector>

using namespace std;


class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = 0;
        for (int a : nums) sum += a;
        int traget = sum - x, left = 0, right = 0, tmp = 0, ret = -1;
        if (traget < 0) return -1;//小细节

        for (right = 0; right < nums.size(); right++)
        {
            tmp += nums[right];//进窗口
            while (tmp > traget)//判断
                tmp -= nums[left++];//出窗口
            if (tmp == traget)
                ret = max(ret, right - left + 1);//更新结果
        }
        if (ret == -1) return -1;//找不到返回-1
        else return nums.size() - ret;//反向求，traget最大时操作数最小
    }
};

int main()
{
    int x1 = 5;
    vector<int> nums1 = { 1,1,4,2,3};
    int result = Solution().minOperations(nums1, x1);
    cout << result << endl;

    return 0;
}