当前位置：首页 > article >正文

【OJ刷题】同向双指针问题

article 2025/1/9 5:19:57

这里是阿川的博客，祝您变得更强

✨ 个人主页：在线OJ的阿川
💖文章专栏：OJ刷题入门到进阶
🌏代码仓库：

写在开头

现在您看到的是我的结论或想法，但在这背后凝结了大量的思考、经验和讨论

在这里插入图片描述

1. 题目介绍

难度：中
题目练习：长度最小的子数组
题目信息：给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的子数组[numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
举个例子： 具体如图1所示

图1 举个例子

2. 题目拆解

本质上：观察规律，利用滑动窗口
特点是：同向双指针，不存在回退
解决方法：同向双指针算法，如图2所示

图2 同向双指针

3. 具体详情

1. 先计算每个具体数的累加总和
2. 判断累加总和与目标值之间的大小关系，从而进行移动判断
3. 返回具体的数组大小值

4. 具体代码

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size(), sum = 0, len = INT_MAX; //一个边界大小，一个是总和，一个是返回的数组大小
        for(int left = 0, right = 0; right < n; right++)
        {
            sum += nums[right]; //每次循环进来先更新总和
            while(sum >= target) //判断移动方向
            {
                len = min(len, right - left + 1);
                sum -= nums[left++];
            }
        }
        return len == INT_MAX ? 0: len; //返回数组大小
    }
};