• 🎥 个人主页：Dikz12
• 🔥个人专栏：Java算法
• 📕格言：那些在暗处执拗生长的花，终有一日会馥郁传香
• 欢迎大家👍点赞✍评论⭐收藏

目录

1.长度最小的子数组

题目解析 

讲解 

 代码实现

 2.无重复字符的最长子串

题目解析 

 讲解

代码实现 

3.最大连续1的个数 III

题目解析 

讲解 

代码实现 

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

题目解析

​编辑讲解 

代码实现 

 5.水果成篮

题目解析 

讲解 

代码实现 

1.长度最小的子数组

题目解析 

讲解 

解法一： 暴力枚举出所有子数组的和. O(n^2)

解法二：利用“滑动窗口”优化.（利用单调性,同向双指针） O(n)

1. left = 0，right = 0
2. 进窗口
3. 判断
4.  出窗口 或者 是更新结果

当sum 小于target时，就进窗口（right++）;

满足判断条件（sum大于等于target）时，此时，更新结果，出窗口，可以⼤胆舍去 left得值然后left++，right也没有回退到left位置的必要了（left++）

 代码实现

public int minSubArrayLen(int target, int[] nums) {         int n = nums.length;        int sum = 0, len = Integer.MAX_VALUE;        for (int left = 0, right = 0; right < n; right++) {             sum += nums[right];            // 进窗口            while (sum >= target) {                 // 更新len                len = Math.min(len, (right - left + 1));                // 出窗口                sum -= nums[left++];            }        }        return len == Integer.MAX_VALUE ? 0 : len;    }

 2.无重复字符的最长子串

题目解析 

 讲解

解法一：暴力枚举 + 哈希表（判断字符是否重复出现）

枚举「从每⼀个位置」开始往后，⽆重复字符的⼦串可以到达什么位置。找出其中⻓度最⼤的即
可。在往后寻找⽆重复⼦串能到达的位置时，可以利⽤「哈希表」统计出字符出现的频次，来判断什么时候⼦串出现了重复元素.

解法二：使用“滑动窗口”来解决.

右端元素 ch 进⼊窗⼝的时候，使用数组模拟哈希来统计这个字符的频次：

• 如果这个字符出现的频次超过1 ，说明窗⼝内有重复元素，那么就从左侧开始划出窗⼝，直到ch 这个元素的频次变为 1 ，然后再更新结果。
• 如果没有超过1 ，说明当前窗⼝没有重复元素，可以直接更新结果
  

代码实现 

public int lengthOfLongestSubstring(String s) {         //转换成字符数组        char[] ch = s.toCharArray();        int ret =0,n = s.length();        //利用ascii码值模拟        int[] hash = new int[128];        for(int left = 0,right = 0; right < n; right++) {             hash[ch[right]]++;            while(hash[ch[right]] > 1) {  //判断                 hash[ch[left++]]--;//出窗口            }            ret = Math.max(ret,right - left + 1);        }        return ret;

3.最大连续1的个数 III

题目解析 

讲解 

 意思就是：找出最长的子数组，且 0 的个数不能超过 k.

解法一： 暴力枚举 + 计数器（统计0出现的次数）

解法二：滑动窗口

1. 定义left=0，right=0 ; count=0 统计0的次数;
2.  进窗口，如果 等于 0，count++; 等于 1，不做处理
3. 判断，当 count 大于 k，出窗口，出的时候，等于 0，count - -；等于 1，不做处理
4. 更新结果. (不满足判断，直接更新结果；否则，先出窗口，在更新)

代码实现 

public int longestOnes(int[] nums, int k) {         int n = nums.length, count = 0, ret = 0;        for (int left = 0, right = 0; right < n; right++) {             if (nums[right] == 0) {                 count++;            }            while (count > k) {  // 判断                if (nums[left] == 0) {                     count--;                }                left++; // 出窗口            }            ret = Math.max(ret, right - left + 1); // 更新结果        }        return ret;    }

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

题目解析

讲解 

正难则反 ：题⽬要求的是数组「左端+右端」两段连续的、和为 x 的最短数组. 转换成求数组内⼀段连续的、和为 sum(nums) - x 的最⻓数组.

 解法：滑动窗口. 

这是的写法就和第一题的时候就很相似了.（求等于target的最长的子数组） 

1.  计算出 target = sum - x的值，target 小于 0，直接返回 -1；（sum为整个数组的和）
2. 进窗口  right++（记录下当前和tmp）
3. 判断. 当tmp大于target时，出窗口，先从tmp中舍去当前位置的值，在left++；
4. 更新结果. 我们要的是 等于target 的子数组长度，需要加上个if条件.

代码实现 

public int minOperations(int[] nums, int x) {         int ret = -1,sum = 0,n = nums.length,tmp = 0;        for(int i : nums) {             sum += i;        }        int target = sum - x;        if(target < 0) {             return -1;        }        for(int left = 0,right = 0; right < n;right++) {             //进窗口            tmp += nums[right];             //判断            while(tmp > target) {                //出窗口              tmp -= nums[left++];            }            if(tmp == target) {                 ret = Math.max(ret,right - left + 1);            }        }        if(ret == -1) {             return -1;        }else{             //ret是sum-x的长度            return n - ret;        }    }

 5.水果成篮

题目解析 

 这么长的小作文，意思就是：找出一个最长的子数组的长度，子数组中不超过两种类型的水果.

讲解 

解法一：暴力枚举 + Map 容器. 

解法二：滑动窗口 .

指针同向移动，可以使用“滑动窗口”.

1.  初始化Map容器（也可以使用数组模拟）,来统计窗⼝内⽔果的种类和数量；
2. 初始化变量：左右指针 left = 0，right = 0，记录结果的变量 ret = 0
3. 进窗口.将当前⽔果放⼊Map中；
4. 判断.当前⽔果进来后，Map的⼤⼩：如果超过 2：将左侧元素滑出窗⼝，并且在Map中将该元素的value减⼀；如果这个元素的value减⼀之后变成了 0，就把该元素从哈希表中删除；
   重复上述两个过程，直到哈希表中的⼤⼩不超过 2；
5.  更新结果

代码实现 

public int totalFruit(int[] fruits) {         int n = fruits.length, ret = 0;        Map<Integer, Integer> map = new HashMap<>();        for (int left = 0, right = 0; right < n; right++) {             int key = fruits[right];            map.put(key, map.getOrDefault(key, 0) + 1);// 进窗口            // 判断            while (map.size() > 2) {                 // 出窗口                int out = fruits[left];                map.put(out, map.get(out) - 1);                if (map.get(out) == 0) {                     map.remove(out);                }                left++;            }            ret = Math.max(ret, right - left + 1);        }        return ret;    }

 数组模拟实现：

public int totalFruit(int[] fruits) {         int n = fruits.length, ret = 0;        int[] map = new int[n+1];        // Map<Integer, Integer> map = new HashMap<>();        for (int left = 0, right = 0,type = 0; right < n; right++) {             int key = fruits[right];            // map.put(key, map.getOrDefault(key, 0) + 1);// 进窗口            if(map[key] == 0) {                 type++; //记录水果种类            }            map[key]++; //进窗口            // 判断            while (type > 2) {                 // 出窗口                int out = fruits[left];                map[out]--;                // map.put(out, map.get(out) - 1);                if (map[out] == 0) {                     type--;                }                left++;            }            ret = Math.max(ret, right - left + 1);        }        return ret;    }