做明星粉丝网站,赤峰做网站,搭建漏洞网站,域名要多少钱一、209:长度最小的子数组
209:长度最小的子数组
思路#xff1a;1、暴力解法#xff1a;两层for循环遍历#xff0c;当sum target时计算子数组长度并与result比较#xff0c;取最小的更新result。提交但是超出了时间限制。 class Solution {public int minSubArray…一、209:长度最小的子数组
209:长度最小的子数组
思路1、暴力解法两层for循环遍历当sum target时计算子数组长度并与result比较取最小的更新result。提交但是超出了时间限制。 class Solution {public int minSubArrayLen(int target, int[] nums) {int result Integer.MAX_VALUE;int sum 0;for (int i 0; i nums.length; i) {sum 0;for (int j i; j nums.length; j) {sum nums[j];if (sum target) {result Math.min(j-i1, result);break;}}}return result Integer.MAX_VALUE ? 0 : result;}
} 2、滑动窗口所谓滑动窗口就是不断的调节子序列的起始位置和终止位置从而得出我们要想的结果。在暴力解法中是一个for循环滑动窗口的起始位置一个for循环为滑动窗口的终止位置用两个for循环 完成了一个不断搜索区间的过程。 只用一个for循环那么这个循环的索引一定是表示 滑动窗口的终止位置。滑动窗口也可以理解为双指针法的一种只不过这种解法更像是一个窗口的移动所以叫做滑动窗口更适合一些。
for循环滑动窗口的终止位置不断更新窗口的起始位置因为窗口里面有多个符合大于target的窗口比如第一个元素如果是负数去掉之后还是大于target所以循环里面的判断条件使用while而不使用if。 不要以为for里放一个while就以为是O(n^2) 主要是看每一个元素被操作的次数每个元素在滑动窗后进来操作一次出去操作一次每个元素都是被操作两次所以时间复杂度是 2 × n 也就是O(n)。 class Solution {public int minSubArrayLen(int target, int[] nums) {int left 0;int sum 0;int result Integer.MAX_VALUE;for (int right 0; right nums.length; right) {sum nums[right];while (sum target) {result Math.min(right-left1, result);sum - nums[left];//这里体现滑动窗口的精髓不断变更i(子序列的起始位置)}}return result Integer.MAX_VALUE ? 0 : result;}
} 二、904.水果成篮
力扣
也是滑动窗口的题目。 class Solution {public int totalFruit(int[] fruits) {// 我们发现形成窗口大小其实是固定的(两个篮子果子种类)// 键为果子类型值为果子数量MapInteger, Integer mapnew HashMap();int left 0;int result 0;for(int right 0; right fruits.length; right) {map.put(fruits[right], map.getOrDefault(fruits[right], 0) 1);// 窗口果子种类超过两种果子了广快弄掉一个种类的果子while(map.size() 2){map.put(fruits[left], map.get(fruits[left]) - 1);if(map.get(fruits[left]) 0){map.remove(fruits[left]);}left;}result Math.max(result, right - left 1);}return result;}
} 三、无重复的最长字串
无重复字符的最长子串https://leetcode.cn/problems/longest-substring-without-repeating-characters/
class Solution {public int lengthOfLongestSubstring(String s) {int len s.length();int res 0;int left 0;MapCharacter,Integer map new HashMap();for(int right 0; right len; right) {if(map.containsKey(s.charAt(right))) {left Math.max(left, map.get(s.charAt(right)) 1);res Math.max(res, right - left 1);}map.put(s.charAt(right), right);}return res;}
}
