【滑动窗口】长度最小的子数组|无重复字符的最长子串|最大连续1的个数 III|将 x 减到 0 的最小操作数_ar

1.题目解析：

2.算法原理

（1）方法一：暴力列举出所有的子数组的和

时间复杂度：o（n**2）：枚举所有子数组o（n**2）

（2）方法二：

利用单调性（两个指针都不回退），使用"同向双指针"（其实就是滑动窗口）来优化

3.代码实现

class solution {
    public int minsubarraylen(int target, int[] nums) {
        int sum = 0;
        int ret = integer.max_value;
        for(int left=0,right=0;right<nums.length;right++) {
            sum+=nums[right];//进窗口
            while(sum>=target) {//判断
                ret = math.min(right-left+1,ret);//更新结果
                sum-=nums[left];
                left++;
            }
        }
        //要考虑特殊情况：不存在
        return ret==integer.max_value ? 0:ret;
    }
}

2. 无重复字符的最长子串 - 力扣（leetcode）

1.题目解析：

2.算法原理

3.代码实现

class solution {
    public int lengthoflongestsubstring(string s) {
        char[] ss = s.tochararray();//字符串转为字符数组
        int[] hash = new int[128]; //用数组模拟哈希表

        int len = 0;
        for(int left=0,right=0;right<s.length();right++) {
            //进窗口
            hash[ss[right]]++;
            while(hash[ss[right]]>1) {//有重复字符
                //删除
                hash[ss[left]]--;
                //出窗口
                left++;
            }
            //更新结果
            len = math.max(len,right-left+1);
        }
        return len;
    }
}

3. 最大连续1的个数 iii - 力扣（leetcode）

1.题目解析：

2.算法原理：

问题转化：找出最长的子数组，0的个数不超过k个

3.代码实现：

class solution {
    public int longestones(int[] nums, int k) {
        int count=0;
        int zero=0;
        for(int left=0,right=0;right<nums.length;right++) {
            //进窗口
            if(nums[right]==0){
                zero++;
            }
            while(zero>k) {//判断：0的个数超过k个
                //出窗口
                if(nums[left]==0) {
                    zero--;
                }
                left++;
            }
            count=math.max(count,right-left+1);
        }
        return count;
    }
}

1658. 将 x 减到 0 的最小操作数 - 力扣（leetcode）

1.题目解析：

2.算法原理：

3.代码实现：

class solution {
    public int minoperations(int[] nums, int x) {
        int sum=0;
        for(int a:nums) sum+=a;
        int sum=0;
        int target = sum-x;
        //处理细节
        if(target<0) {
            return -1;
        }
        int ret=-1;
        for(int left=0,right=0;right<nums.length;right++) {
            //进窗口
            sum+=nums[right];
            //判断
            while(sum>target) {
                //出窗口
                sum-=nums[left++];
            }
            //更新结果
            if(sum==target) {
                ret=math.max(right-left+1,ret);
            }
        }
        return (ret==-1)?(-1):(nums.length-ret);
    }
}