- 🎥 个人主页:Dikz12
- 🔥个人专栏:Java算法
- 📕格言:那些在暗处执拗生长的花,终有一日会馥郁传香
- 欢迎大家👍点赞✍评论⭐收藏
目录
1.长度最小的子数组
题目解析
讲解
代码实现
2.无重复字符的最长子串
题目解析
讲解
代码实现
3.最大连续1的个数 III
题目解析
讲解
代码实现
4.将 x 减到 0 的最小操作数
题目解析
编辑讲解
代码实现
5.水果成篮
题目解析
讲解
代码实现
1.长度最小的子数组
题目解析
讲解
解法一: 暴力枚举出所有子数组的和. O(n^2)
解法二:利用“滑动窗口”优化.(利用单调性,同向双指针) O(n)
- left = 0,right = 0
- 进窗口
- 判断
- 出窗口 或者 是更新结果
当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出现的次数)
解法二:滑动窗口
- 定义left=0,right=0 ; count=0 统计0的次数;
- 进窗口,如果 等于 0,count++; 等于 1,不做处理
- 判断,当 count 大于 k,出窗口,出的时候,等于 0,count - -;等于 1,不做处理
- 更新结果. (不满足判断,直接更新结果;否则,先出窗口,在更新)
代码实现
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的最长的子数组)
- 计算出 target = sum - x的值,target 小于 0,直接返回 -1;(sum为整个数组的和)
- 进窗口 right++(记录下当前和tmp)
- 判断. 当tmp大于target时,出窗口,先从tmp中舍去当前位置的值,在left++;
- 更新结果. 我们要的是 等于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 容器.
解法二:滑动窗口 .
指针同向移动,可以使用“滑动窗口”.
- 初始化Map容器(也可以使用数组模拟),来统计窗⼝内⽔果的种类和数量;
- 初始化变量:左右指针 left = 0,right = 0,记录结果的变量 ret = 0
- 进窗口.将当前⽔果放⼊Map中;
- 判断.当前⽔果进来后,Map的⼤⼩:如果超过 2:将左侧元素滑出窗⼝,并且在Map中将该元素的value减⼀;如果这个元素的value减⼀之后变成了 0,就把该元素从哈希表中删除;
重复上述两个过程,直到哈希表中的⼤⼩不超过 2; - 更新结果
代码实现
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;
}