643. 子数组最大平均数 I
以下会超时 因为每个子数组都要计算一次平均数,复杂度为O(n^2)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| class Solution { public double findMaxAverage(int[] nums, int k) { if(nums.length==1) return (double)nums[0]; double maxm = 0; int fast = k-1; int slow = 0; while(fast<nums.length){ double temp = 0; for(int i=0;i<k;i++){ temp+= nums[slow+i]; } temp = temp/k; if(temp>maxm) maxm = temp; fast++; slow++; } return maxm; } }
|
以下为官方答案 两头更新 中间的保留
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| class Solution { public double findMaxAverage(int[] nums, int k) { int sum = 0; for(int i=0;i<k;i++){ sum+=nums[i]; } int maxm = sum; for(int j=k;j<nums.length;j++){ sum = sum - nums[j-k] + nums[j]; if(sum>maxm) maxm = sum; } return 1.0*maxm/k; } }
|
1004. 最大连续1的个数 III
⭐
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| class Solution { public int longestOnes(int[] nums, int k) { int right = 0; int res=0; int left = 0; int count = 0; while(right<nums.length){ if(nums[right]==0) count++; while(count>k){ if(nums[left]==0) count--; left++; } res = Math.max(res,right-left+1); right++; } return res; } }
|
1493. 删掉一个元素以后全为 1 的最长子数组
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| class Solution { public int longestSubarray(int[] nums) { int right = 0,left = 0; int res = 0; int c=0; while(right<nums.length){ if(nums[right]==0) c++; while(c>1){ if(nums[left]==0) c--; left++; } res =Math.max(res,right-left); right++; } return res; } }
|
右指针主动走 左指针通过判断条件被动走
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| def findSubArray(nums): N = len(nums) left, right = 0, 0 sums = 0 res = 0 while right < N: sums += nums[right] while 区间[left, right]不符合题意: sums -= nums[left] left += 1 res = max(res, right - left + 1) right += 1 return res
|
3. 滑动窗口
☆
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| class Solution { public int lengthOfLongestSubstring(String s) { Map<Character,Integer> map = new HashMap<Character,Integer>(); int maxm = 0; int left=0; for(int i=0;i<s.length();i++){ if(map.containsKey(s.charAt(i))){ left = Math.max(left,map.get(s.charAt(i))); } map.put(s.charAt(i),i); maxm = Math.max(maxm,i-left+1); } return maxm; } }
|
438. 比特位计数
很棒!自己调试ac的
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| class Solution { public List<Integer> findAnagrams(String s, String p) { char charp[] = p.toCharArray(); Arrays.sort(charp); List<Integer> list = new ArrayList<Integer>(); String p1 = new String(charp); int left=0; int right=p.length()-1; while(right<s.length()){ String temp = s.substring(left,right+1); char charpp[] = temp.toCharArray(); Arrays.sort(charpp); String p2 = new String(charpp); if(p1.equals(p2)){ list.add(left); } left++; right++; } return list; } }
|