网站建设与运营成本,二级域名分发网站,网站建设面板,网页设计就业方向这里写目录标题 209.长度最小的子数组题目思路代码 3. 无重复字符的最长子串#xff08;medium#xff09;题目思路 11. 最大连续 1 的个数 III题目思路 1658. 将 x 减到 0 的最⼩操作数题目思路代码 904. 水果成篮题目思路代码 438.找到字符串中所有字母的异位词题目思路代码… 这里写目录标题 209.长度最小的子数组题目思路代码 3. 无重复字符的最长子串medium题目思路 11. 最大连续 1 的个数 III题目思路 1658. 将 x 减到 0 的最⼩操作数题目思路代码 904. 水果成篮题目思路代码 438.找到字符串中所有字母的异位词题目思路代码 209.长度最小的子数组
题目 思路
因为数组中的数字都是正数,所以我们可以利用单调性使用滑动窗口的方式来实现用两个指针left和right维护一段区间 当right向右移动时,这个区间内的和增大,当left向右移动时,这个区间内的和减少,这就是这道题目的单调性,我们就可以利用单调性来解题
代码
class Solution {public int minSubArrayLen(int target, int[] nums) {int sum 0;int ret Integer.MAX_VALUE;for(int left 0, right 0; right nums.length; right){sum nums[right];//如果窗口内元素大于target此时就要移动left指针,直到窗口内值小于target,并且过程中不断更新结果while(sum target){ret Math.min(ret,right - left 1);sum - nums[left];}}return ret Integer.MAX_VALUE ? 0 : ret;}
}3. 无重复字符的最长子串medium
题目 思路
利用滑动窗口维护一个区间来找最长字串,利用哈希表来检查是否有重复元素创建left指针和right指针,right指针每次向后走,就将当前位置的字符放在哈希表中,如果,此时这个元素在哈希表中出现次数超过一次,就移动left指针,每次移动left指针都要将left指针所指向的位置的元素删除,直到这个元素只出现一次,再次移动right指针
class Solution {public int lengthOfLongestSubstring(String s) {int[] hash new int[128];//数组模拟哈希表int ret 0;char[] arr s.toCharArray();for(int left 0, right 0; right s.length(); right){hash[arr[right]];//每次将right位置的元素放在哈希表中while(hash[arr[right]] 1){//当放进去的元素重复时,就开始移动左指针删除做指针指向的元素hash[arr[left]]--;}ret Math.max(ret,right-left1);}return ret;}
}11. 最大连续 1 的个数 III
题目 思路
根据题意翻转0,我们可以将问题转化为数组中最长的不超过k个0的序列此时根据滑动窗口就可以很好的解决这道题目
class Solution {public int longestOnes(int[] nums, int k) {int cnt 0;int ret 0;for(int left 0,right 0; right nums.length; right){//如果进窗口的元素是0,则0计数器1if(nums[right] 0){cnt;}//此时窗口中0的个数超出了要求,移动左指针left调整窗口,使其符合题意while(cnt k 1){if(nums[left] 0){cnt--;}}ret Math.max(ret,right-left1);}return ret;}
}1658. 将 x 减到 0 的最⼩操作数
题目 思路
这道题通过题意,可以转化为和为sum-x的最大子数组使用滑动窗口来解决此题
代码
class Solution {public int minOperations(int[] nums, int x) {int sum 0;for(int i 0;i nums.length; i){sum nums[i];}int k sum - x;if(k 0){return -1;}int ret -1;sum 0;for(int left 0, right 0; right nums.length; right){sum nums[right];while(sum k){sum - nums[left];}if(sum k){ret Math.max(ret,right - left 1);}}if(ret -1){return -1;}return nums.length - ret;}
}904. 水果成篮
题目 思路
题目已经暗示我们使用滑动窗口来解决问题,把问题转化成最长的只有两种数字的字串通过哈希表的方式来记录是否超出种类
代码
class Solution {public int totalFruit(int[] fruits) {MapInteger,Integer hash new HashMap();int ret 0;for(int left 0, right 0; right fruits.length; right){hash.put(fruits[right],hash.getOrDefault(fruits[right],0) 1);while(hash.size() 2){hash.put(fruits[left],hash.get(fruits[left]) -1);if(hash.get(fruits[left]) 0){hash.remove(fruits[left]);}left;}ret Math.max(ret,right - left 1);}return ret;}
}438.找到字符串中所有字母的异位词
题目 思路
通过滑动窗口的方式,窗口大小恒为p字符串的长度,用哈希表分别存放两个字符串的每个字符,如果两个哈希表相同,则将这个窗口左下标放在结果集中
代码
class Solution {public ListInteger findAnagrams(String s, String p) {ListInteger ret new ArrayList();MapCharacter,Integer start new HashMap();MapCharacter,Integer end new HashMap();for(int i 0; i p.length(); i){start.put(p.charAt(i),start.getOrDefault(p.charAt(i), 0) 1);}for(int left 0, right 0; right s.length(); right){end.put(s.charAt(right),end.getOrDefault(s.charAt(right), 0) 1);if(right - left 1 p.length()){if(start.equals(end)){ret.add(left);if(end.get(s.charAt(left)) 1){end.remove(s.charAt(left));}else {end.put(s.charAt(left),end.getOrDefault(s.charAt(left), 0) - 1);}}else{end.put(s.charAt(left),end.getOrDefault(s.charAt(left), 0) - 1);if(end.get(s.charAt(left)) 0){end.remove(s.charAt(left));}}left;}}return ret;}
}
