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

实用指南：【LeetCode精选算法】滑动窗口专题一

news 2026/5/11 20:28:49

核心思想：滑动窗口（同向双指针）
具体步骤：
初始化left=0, right=0, sum=0, minLen=∞
右指针right向右扩展窗口，累加sum
当sum ≥ target时：
更新minLen
左指针left向右收缩窗口，直到sum < target
重复直到right到达数组末尾
时间复杂度：O(n)，每个元素最多被访问两次
空间复杂度：O(1)

class Solution {public int minSubArrayLen(int target, int[] nums) {int left = 0, right = 0;int sum = 0;int minLength = Integer.MAX_VALUE;while (right < nums.length) {// 扩展窗口：右指针右移sum += nums[right];// 收缩窗口：当窗口和≥target时，尝试缩小窗口while (sum >= target) {// 更新最小长度minLength = Math.min(minLength, right - left + 1);// 收缩窗口：左指针右移sum -= nums[left];left++;}// 继续扩展窗口right++;}// 如果没找到符合条件的子数组，返回0return minLength == Integer.MAX_VALUE ? 0 : minLength;}
}

2. 无重复字符的最长子串（3. Longest Substring Without Repeating Characters）

题目链接：LeetCode 3

详细解题思路：

核心思想：滑动窗口 + 哈希表记录字符出现次数
具体步骤：
初始化left=0, right=0，哈希数组hash[128]
右指针right向右扩展，对应字符计数加1
当某个字符计数>1时，说明出现重复：
左指针left向右移动，直到重复字符的计数降为1
同时更新哈希表
每次循环更新最大长度
优化：可以用哈希表记录字符最后出现的位置，直接跳转到重复字符的下一位
时间复杂度：O(n)，空间复杂度：O(字符集大小)

class Solution {public int lengthOfLongestSubstring(String s) {// 哈希表，记录每个字符出现的次数int[] hash = new int[128];int left = 0, right = 0;int maxLength = 0;while (right < s.length()) {// 右指针字符进入窗口char inChar = s.charAt(right);hash[inChar]++;// 如果当前字符出现次数>1，说明有重复while (hash[inChar] > 1) {// 左指针字符移出窗口char outChar = s.charAt(left);hash[outChar]--;left++;}// 更新最大长度maxLength = Math.max(maxLength, right - left + 1);// 右指针右移right++;}return maxLength;}
}

3. 最大连续1的个数 III（1004. Max Consecutive Ones III）

题目链接：LeetCode 1004

详细解题思路：

核心思想：滑动窗口，维护窗口内0的个数≤k
问题转化：求最长子数组，其中0的个数不超过k
具体步骤：
初始化left=0, right=0, zeroCount=0
右指针right扩展窗口：
如果nums[right]==0，zeroCount++
当zeroCount > k时，收缩窗口：
如果nums[left]==0，zeroCount--
left++
更新最大窗口长度
时间复杂度：O(n)，空间复杂度：O(1)

class Solution {public int longestOnes(int[] nums, int k) {int left = 0, right = 0;int zeroCount = 0;  // 窗口内0的个数int maxLength = 0;while (right < nums.length) {// 右指针扩展窗口if (nums[right] == 0) {zeroCount++;}// 如果0的个数超过k，收缩窗口while (zeroCount > k) {if (nums[left] == 0) {zeroCount--;}left++;}// 更新最大长度maxLength = Math.max(maxLength, right - left + 1);// 右指针右移right++;}return maxLength;}
}

4. 将x减到0的最小操作数（1658. Minimum Operations to Reduce X to Zero）

题目链接：LeetCode 1658

详细解题思路：

核心思想：问题转化 + 滑动窗口
问题转化：
移除数组两端元素，使和为x
等价于：找到数组中间最长的子数组，使其和为sum - x
最小操作数 = n - 最长子数组长度
具体步骤：
计算数组总和totalSum
目标子数组和target = totalSum - x
如果target < 0，直接返回-1
使用滑动窗口找到和为target的最长子数组
边界情况：
如果target == 0，需要移除整个数组
如果找不到和为target的子数组，返回-1
时间复杂度：O(n)，空间复杂度：O(1)

class Solution {public int minOperations(int[] nums, int x) {int totalSum = 0;for (int num : nums) {totalSum += num;}int target = totalSum - x;// 如果目标值小于0，不可能实现if (target < 0) return -1;// 如果目标值等于0，需要移除所有元素if (target == 0) return nums.length;int left = 0, right = 0;int currentSum = 0;int maxSubarrayLength = -1;while (right < nums.length) {// 扩展窗口currentSum += nums[right];// 收缩窗口：如果当前和大于目标值while (currentSum > target && left <= right) {currentSum -= nums[left];left++;}// 如果找到目标子数组，更新最大长度if (currentSum == target) {maxSubarrayLength = Math.max(maxSubarrayLength, right - left + 1);}// 右指针右移right++;}// 如果没找到符合条件的子数组if (maxSubarrayLength == -1) return -1;// 最小操作数 = 总长度 - 最长子数组长度return nums.length - maxSubarrayLength;}
}

查看全文

http://www.jsqmd.com/news/384453/