day54【代码随想录】二刷数组

---

前言

1、二分查找
2、移除元素
3、有序数组的平方
4、合并两个有序数组
5、长度最小的子数组
6、水果成篮
7、最小覆盖字串
8、最大连续1的个数|||
9、无重复字符的最长字串

---

一、二分查找（力扣724）

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

class Solution {public int search(int[] nums, int target) {int left;int right;int mid;int index = -1;left = 0;right = nums.length-1;while(left<=right){mid = (left+right)/2;if(nums[mid]>target){right=mid-1;}else if(nums[mid]<target){left=mid+1;}else if (nums[mid]==target){return mid;}}return index;    }
}

二、移除元素（力扣27）【双指针】

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

class Solution {public int removeElement(int[] nums, int val) {int fast;int slow;for(fast=0,slow=0; fast<nums.length;){if(nums[fast]==val){fast++;}else{nums[slow++] = nums[fast++];}}return slow;}
}

三、有序数组的平方（力扣977）【双指针】

有一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

暴力求解省略：
每个数平方之后，排个序，美滋滋
时间复杂度：O(n + nlogn)，

class Solution {public int[] sortedSquares(int[] nums) {int[] res = new int[nums.length];int slow=0;int fast=nums.length-1;int index = nums.length-1;for(slow=0,fast=nums.length-1;slow<=fast;){if(nums[slow]*nums[slow]>=nums[fast]*nums[fast]){res[index--]=nums[slow]*nums[slow]; slow++;}else{res[index--]=nums[fast]*nums[fast];fast--;}}return res;}
}

时间复杂度：O(n)

四、合并两个有序数组（力扣88）

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int i = m-1;int j = n-1;int index = nums1.length-1;for(;j>=0;){if(i<0||nums1[i]<=nums2[j]){nums1[index--] = nums2[j];j--;}else{nums1[index--] = nums1[i];i--;}}}
}

注意要考虑边界条件：

五、长度最小的子数组（力扣209）【滑动窗口】

给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

暴力求解：
两个for循环，然后不断的寻找符合条件的子序列，时间复杂度很明显是O(n^2)。

		for (int i = 0; i < nums.length; i++) { // 设置子序列起点为isum = 0;for (int j = i; j < nums.length; j++) { // 设置子序列终止位置为jsum += nums[j];if (sum >= s) { // 一旦发现子序列和超过了s，更新resultsubLength = j - i + 1; // 取子序列的长度result = result < subLength ? result : subLength;break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break}}

滑动窗口：
滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果
在暴力解法中，是一个for循环滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用两个for循环 完成了一个不断搜索区间的过程。那么滑动窗口用一个for循环来完成这个操作。

滑动窗口问题一：如果用一个for循环，那么应该表示 滑动窗口的起始位置，还是终止位置
滑动窗口问题二：如何遍历剩下的终止位置？
滑动窗口问题三：滑动窗口的起始位置如何移动？

class Solution {public int minSubArrayLen(int target, int[] nums) {int left =0;int right;int subLength = Integer.MAX_VALUE;     int res=0;//滑动窗口一个for循环表示（滑动窗口终止位置）for(right=0;right<nums.length;right++){res+=nums[right];while(res>=target){subLength = Math.min(subLength,right-left+1);res -= nums[left++];}}return subLength == Integer.MAX_VALUE? 0:subLength;}
}

六、水果成篮（力扣904）【滑动窗口】****

fruits[i] 是第 i 棵树上的水果 种类 。
想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回可以收集的水果的最大数目。

白话题意：求满足某个条件（数组值最多就两类的连续数组，例如[1,2,2,1,2]）的最长数组长度

class Solution {public int totalFruit(int[] fruits) {HashMap<Integer,Integer> map = new HashMap<>();int res =0;int i=0;int j=0;while(j<fruits.length){//判断当前是否满足条件？map.put(fruits[j],map.getOrDefault(fruits[j],0)+1);while(map.size()>2){//不满足条件//把加进来i的都移出去map.put(fruits[i],map.get(fruits[i])-1);if(map.get(fruits[i])==0){map.remove(fruits[i]);}i++;}//更新结果res = Math.max(res,j-i+1);j++;}return res;}
}

For me 比较考验map数组的使用

七、最小覆盖子串（力扣76）【滑动窗口】****

一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

同样是滑动窗口，这两题有什么区别？区别在于904题求的是最大滑窗，而本题求的是最小滑窗

class Solution {public String minWindow(String s, String t) {//最小滑动窗口：int[] need = new int[128];//记录t中需要字符的个数for(int i =0; i<t.length();i++){need[t.charAt(i)]++;}int i=0;int j=0;String res = "";int count = t.length();int size = Integer.MAX_VALUE;int start =0;while(j<s.length()){//判断是否满足条件if(need[s.charAt(j)]>0){count--;}need[s.charAt(j)]--; //把右边字符加入窗口while(count==0){ //满足条件 窗口中已经包含所有元素// 一旦满足条件，尽可能的压缩i，并且不断更新结果//更新结果值while(i<j && need[s.charAt(i)]<0){ //压缩左窗口need[s.charAt(i)]++;i++;}if(j-i+1<size){size = j-i+1;  //更新结果值start = i;  //需要记录窗口的起始位置}need[s.charAt(i)]++;i++;count++;}j++;}return size == Integer.MAX_VALUE? "" :s.substring(start,start+size);}
}

窗口扩展时寻找可行解，窗口收缩时优化可行解。而且这个题可行解每次都是一个

八、最大连续1的个数 III（力扣1004）【滑动窗口】

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。
最大滑动窗口：

class Solution {public int longestOnes(int[] nums, int k) {int i =0;int j =0;int size = 0;int zeroCount =0;while(j<nums.length){ //滑动窗口终止位置//判断是否满足条件  把k个0翻转为1if(nums[j]==0 ){zeroCount++;}//不满足条件：while(zeroCount>k){//缩小左边界，一旦左边界满足 就退出循环，尽可能取到窗口的最大长度if(nums[i]==0){zeroCount--;}i++;}//更新结果size = Math.max(size,j-i+1);j++;}return size;}
}

九、无重复字符的最长子串（力扣3）【滑动窗口】****

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

取滑动窗口最大值：

class Solution {public int lengthOfLongestSubstring(String s) {if(s.length()==0) return 0;//最大滑动窗口int i=0;int j=0;int size = 0;HashMap<Character,Integer> map = new HashMap<>();while(j<s.length()){if(map.containsKey(s.charAt(j))){ //看当前的字符串中是否有重复的i = Math.max(i,map.get(s.charAt(j))+1);}map.put(s.charAt(j),j);size = Math.max(size,j-i+1);j++;}return size;}
}

---

总结

滑动窗口模板：
来源：滑动窗口模板参考链接

最小滑窗模板：给定数组 nums，定义滑窗的左右边界 i, j，求满足某个条件的滑窗的最小长度。

while j < len(nums):判断[i, j]是否满足条件while 满足条件：不断更新结果(注意在while内更新！)i += 1 （最大程度的压缩i，使得滑窗尽可能的小）j += 1

最大滑窗模板：给定数组 nums，定义滑窗的左右边界 i, j，求满足某个条件的滑窗的最大长度。

while j < len(nums):判断[i, j]是否满足条件while 不满足条件：i += 1 （最保守的压缩i，一旦满足条件了就退出压缩i的过程，使得滑窗尽可能的大）不断更新结果（注意在while外更新！）j += 1