同向双指针（滑动窗口）算法

本文主要是介绍同向双指针（滑动窗口）算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

209. 长度最小的子数组

这里的更新结果就题来定

class Solution {public int minSubArrayLen(int target, int[] nums) {int sum = 0;int len = 0;int f = 0;for(int left = 0, right = 0; right < nums.length;){//求和sum += nums[right];while(sum >= target){//lenint t = right - left + 1; if(f == 0 ){len = t;}if(t < len ){len = right - left +1;}f = 1;left++;// if(left >= nums.length){//     break;// }sum -= nums[left-1];}//if(right < nums.length){right++;//}// if(left == nums.length){//     break;// }}return len;}
}

我在处理第一次len得到长度时使用的flag，老师用的时最大值，思路可以借鉴

 

先暴力枚举分析所有情况，做这种题都要这样。根据枚举优化得到滑动窗户做法 

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

 

class Solution {public int lengthOfLongestSubstring(String s) {Set<Character> set = new HashSet<Character>();int n = s.length();int len = 0;for(int left = 0, right = 0; right < n;right++){while(right > 0 && set.contains(s.charAt(right))){set.remove(s.charAt(left));left++;}set.add(s.charAt(right));len = Math.max(len, right -left +1);}return len;}
}

什么时候更新len有点难，多想一下过程的思路 

 

这里用数组来当hash，空间复杂度为O(1),但如果new hash 就是O(N)

1004. 最大连续1的个数 III 

 

 虽然是两层循环，但时间复杂度时O(N),空间复杂度O(1)

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

class Solution {public int minOperations(int[] nums, int x) {int s= 0;for(int i = 0; i< nums.length; i++){s += nums[i];}int target = s - x, len = 0;if(target == 0){return nums.length;}if(target < 0){return -1;}int f = 0;for(int left = 0, right = 0, sum = 0; right < nums.length; right++ ){sum += nums[right];while(sum >= target){if(sum == target){len = Math.max(len, right - left + 1);sum -= nums[left];left++;f = 1;}else{sum -= nums[left];left++;}}}return f == 1 ? nums.length - len : -1;}
}

如果数组中有0 负数就不能用滑动窗口

这篇关于同向双指针（滑动窗口）算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---