数组刷题<下>套路分析
- 2019 年 10 月 6 日
- 筆記
数组刷题<下>套路分析
一、双索引技术-对撞指针1.167. 两数之和 II – 输入有序数组2. 345. 反转字符串中的元音字母3.344. 反转字符串4.125. 验证回文串5.11. 盛最多水的容器二、双索引技术-滑动窗口1.209. 长度最小的子数组2.438. 找到字符串中所有字母异位词3.76. 最小覆盖子串
一、双索引技术-对撞指针
类似题目：
- 167. 两数之和 II – 输入有序数组
- 345. 反转字符串中的元音字母
- 344. 反转字符串
- 125. 验证回文串
- 11. 盛最多水的容器
注意的问题：
- 定义前后指针
- 向中间靠拢
1.167. 两数之和 II – 输入有序数组
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
- 返回的下标值（index1 和 index2）不是从零开始的。
- 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
实现思路：
使用双索引技术-对撞指针：
- 一般会是大于或者小于。
- 如果大i++ 小 j–
- 两个索引在往中间走。对撞指针。
实现：
class Solution { public int[] twoSum(int[] numbers, int target) { int[] res=new int[2]; int i=0,j=numbers.length-1; while(i<j){ if(numbers[i]+numbers[j]==target){ res[0]=i+1; res[1]=j+1; break; }else if(numbers[i]+numbers[j]>target){ j--; }else{ i++; } } return res; } }
2. 345. 反转字符串中的元音字母
编写一个函数，以字符串作为输入，反转该字符串中的元音字母。
示例 1:
输入: "hello" 输出: "holle"
示例 2:
输入: "leetcode" 输出: "leotcede"
说明: 元音字母不包含字母"y"。
实现思路：
使用双索引技术-对撞指针：
- 两个索引在往中间走。对撞指针。
实现：
这道题难点在于语言的熟悉度。比如在下面java中可以用匿名函数来创建HashMap并初始化。中间使用s.charAt(i)函数获取每个字符，最后将char数组转为String。
class Solution { public String reverseVowels(String s) { int i=0,j=s.length()-1; HashMap<Character,Integer> hashMap = new HashMap<Character, Integer>(){ { put('a',0);put('A',0);put('e',0);put('E',0);put('i',0); put('I',0);put('o',0);put('O',0);put('u',0);put('U',0); } }; char[] str = new char[s.length()]; while(i<=j){ if(hashMap.getOrDefault(s.charAt(i),-1)==-1){ str[i]=s.charAt(i); i+=1; continue; } if(hashMap.getOrDefault(s.charAt(j),-1)==-1){ str[j]=s.charAt(j); j-=1; continue; } str[i]=s.charAt(j); str[j]=s.charAt(i); i+=1; j-=1; } return String.valueOf(str); } }
3.344. 反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：["h","e","l","l","o"] 输出：["o","l","l","e","h"]
示例 2：
输入：["H","a","n","n","a","h"] 输出：["h","a","n","n","a","H"]
实现思路：
使用双索引技术-对撞指针：
- 两个索引在往中间走。对撞指针。
实现：
两边交换即可。
class Solution { public void reverseString(char[] s) { int i=0,j=s.length-1; char temp; while(i<j){ temp=s[i]; s[i]=s[j]; s[j]=temp; i++; j--; } } }
4.125. 验证回文串
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama" 输出: true
示例 2:
输入: "race a car" 输出: false
实现思路：
使用双索引技术-对撞指针：
- 两个索引在往中间走。对撞指针。
实现：
两边往中间走即可。
class Solution { public boolean isPalindrome(String s) { int i=0,j=s.length()-1; s = s.toLowerCase(); while(i<j){ if(!((s.charAt(i) >= '0' && s.charAt(i) <= '9') || (s.charAt(i) >= 'a' && s.charAt(i) <= 'z'))){ i++; continue; } if(!((s.charAt(j) >= '0' && s.charAt(j) <= '9') || (s.charAt(j) >= 'a' && s.charAt(j) <= 'z'))){ j--; continue; } if(s.charAt(i)!=s.charAt(j)) return false; i++; j--; } return true; } }
上述是吧字符串全部转小写了，当然也可以在比较中转：
class Solution { public static boolean isPalindrome(String s) { int i = 0, j = s.length() - 1; while (i < j) { if (!((s.charAt(i) >= '0' && s.charAt(i) <= '9') || (s.charAt(i) >= 'a' && s.charAt(i) <= 'z') || (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z'))) { i++; continue; } if (!((s.charAt(j) >= '0' && s.charAt(j) <= '9') || (s.charAt(j) >= 'a' && s.charAt(j) <= 'z') || (s.charAt(j) >= 'A' && s.charAt(j) <= 'Z'))) { j--; continue; } if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) return false; i++; j--; } return true; } }
5.11. 盛最多水的容器
给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
img
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
实现思路：
使用双索引技术-对撞指针：
- 两个索引在往中间走。对撞指针。
实现：
使用双指针，选择最小高度乘以间距即可。
class Solution { public int maxArea(int[] height) { int left=0,right=height.length-1; int area=0; while(left<right){ if(height[left]<height[right]){ area=Math.max((right-left)*height[left],area); left++; }else{ area=Math.max((right-left)*height[right],area); right--; } } return area; } }
上述简化版：
class Solution { public int maxArea(int[] height) { int left=0,right=height.length-1; int area=0; while(left<right){ area=Math.max(area,(right-left)*Math.min(height[left],height[right])); if(height[left]<height[right]){ left++; }else{ right--; } } return area; } }
二、双索引技术-滑动窗口
类似题目：
- 209. 长度最小的子数组
- 438. 找到字符串中所有字母异位词
- 76. 最小覆盖子串
注意的问题：
- 如何维护窗口？
1.209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3] 输出: 2 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
进阶:
如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
实现思路：
当窗口内的值大于等于目标值，则压缩窗口，左边界向右压缩，否则的话右边界扩容。
注意边界点：右边界的index不能超过数组的最大值，另外右边界与做左边界都要指向计算和的当前元素，所以右窗口j从-1开始，先j++，这样可以保证每次窗口的总和的右边界是与j一致！
实现：
class Solution { public int minSubArrayLen(int s, int[] nums) { int i=0,j=-1; int n=nums.length; int number=n+1; int total=0; while(i<n){ if(j+1<n && total<s){ j++; total+=nums[j]; }else { total-=nums[i]; i++; } //获取每次结果的窗口长度 if(total>=s){ if(number>j-i+1){ number=j-i+1; } } } //若不变，则没有找到 if (number==n+1){ return 0; } return number; } }
滑动窗口升级版1：
class Solution { public int minSubArrayLen(int s, int[] nums) { int i=0,j=-1; int n=nums.length; int number=0; int total=0; while(i<n){ if(j+1<n && total<s){ j++; total+=nums[j]; }else { total-=nums[i]; i++; } //获取每次结果的窗口长度 if(total>=s){ number=number==0?j-i+1:Math.min(j-i+1,number); } } return number; } }
滑动窗口升级版2：
class Solution { public int minSubArrayLen(int s, int[] nums) { int i=0; int sum=0; int number=0; for (int j=0;j<nums.length;j++){ sum+=nums[j]; while(sum>=s){ number=number==0?j-i+1:Math.min(j-i+1,number); sum-=nums[i++]; } } return number; } }
除了上述O(n)时间复杂度，题目中说了O(nlogn)呢？
实现思路：
二分法:
时间复杂度：O(nlogn)，空间复杂度O(n)。
思路：
将原先数组所有数字累加求和得到一个新数组，例如：
nums=[2,3,1,2,4,3] parNums=[0,2,5,6,8,12,15]
然后循环parNums，对每一个数组中的index对应的值，利用二分法找到最小的窗口。
举个例子：
nums=[2,3,1,2,4,3] parNums=[0,2,5,6,8,12,15] -------------- i=0时 -------------- 第一轮 left=0,right=6 left<right,计算出mid=3，此时对应的值为6,mid距离i的和也就是6<7， 调整left=mid+1=4。 第二轮 left=4,right=6 left<right,计算出mid=5，此时对应的值为12，mid距离i的和也就是12>7， 调整right=mid-1。 是不是上述可以看作是查找7的二分法，那么后面依次类推即可。 当然left调整也可以是left++，right调整也可以是right--，也可以AC,但是效率会低一些！ -------------- ......
实现：
循环+二分
public class Solution { public int minSubArrayLen(int s, int[] nums) { int[] parNums = new int[nums.length+1]; //构造nums元素依次累加数组 for(int i=1;i<parNums.length;i++){ parNums[i]=parNums[i-1]+nums[i-1]; } int min=0; for(int i=0;i<parNums.length;i++){ int left=i; int right=parNums.length-1; while(left<=right){ int mid=left+(right-left)/2; int subSum=parNums[mid]-parNums[i]; if(subSum>=s){ right=mid-1; //可以换成right--; min=min==0?mid-i:Math.min(min,mid-i); }else{ left=mid+1; //可以换成left++; } } } return min; } }
2.438. 找到字符串中所有字母异位词
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：
- 字母异位词指字母相同，但排列不同的字符串。
- 不考虑答案输出的顺序。
示例 1:
输入: s: "cbaebabacd" p: "abc" 输出: [0, 6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
示例 2:
输入: s: "abab" p: "ab" 输出: [0, 1, 2] 解释: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。 起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。 起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。
实现思路：
字母异位数指的是：字母异位词指字母相同，但排列不同的字符串。所以只要满足字母异位数，那么p字符串的每个字符肯定会在字符串中出现！
实现：
题目中提到只考虑小写字母，那么创建一个数组长度包含所有小写字母大小，这里创建26个长度数组。使用ch-'a'来存储每个字符与a字符的距离也就是一个int值。
循环s-p次，也就是让p当作窗口扫描s字符串，然后在s中截取子串，并查看这个字串中的每个字符是否在p中存在(或者说p中的字符是否在子串)，这个判断是通过对字串的每个字符累加，然后在p中去减，如果是>=0,那么肯定是字母异位词，<0肯定不是字母异位词。最后把子串开始索引加入list中即可。
class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> res = new ArrayList<>(); if(s==null || p==null||s.length()<p.length()) return res; for(int i=0;i<s.length()-p.length()+1;i++){ if(isAn(s.substring(i,i+p.length()),p)){ res.add(i); } } return res; } public boolean isAn(String s,String p){ int[] arr= new int[26]; for(char ch:s.toCharArray()){ arr[ch-'a']++; } for(char ch:p.toCharArray()){ arr[ch-'a']--; if(arr[ch-'a']<0) { return false; } } return true; } }
对上述优化，上述代码在取子串后调用isAn函数的时候每次都会做循环，也就是连续几个递进会有重复的循环操作，所以效率非常低。
实现思路：
第一个循环让arr数组统计字符串p的每个字符个数，第二个循环，让滑动窗口达到p的长度，并计算第一个窗口是否满足字母异位词。第三个循环是根据s中的字符来调整窗口的左右边界。
实现：
class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> list = new ArrayList<>(); if(s==null || p==null || s.length()<p.length()) return list; int[] arr = new int[26]; for(int i=0;i<p.length();i++){ arr[p.charAt(i)-'a']++; } int p_len=p.length(); int left=0,right=p.length(); for(int i=0;i<p.length();i++){ arr[s.charAt(i)-'a']--; if (arr[s.charAt(i)-'a']>=0) p_len--; } if(p_len==0) list.add(0); while(right<s.length()){ if(arr[s.charAt(left)-'a']>=0) p_len++; arr[s.charAt(left)-'a']++; left++; arr[s.charAt(right)-'a']--; if (arr[s.charAt(right)-'a']>=0) p_len--; right++; if(p_len==0) list.add(left); } return list; } }
实现思路：
使用一个数组arr存储p字符串的每个字符出现的个数。循环字符串s，right表示窗口的右边界，left表示窗口的左边界，根据s中每个窗口内的字符是否存在在arr中来调整左右边界。
实现：
class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> list = new ArrayList<>(); if(s==null || p==null || s.length()<p.length()) return list; int[] arr = new int[26]; for(int i=0;i<p.length();i++){ arr[p.charAt(i)-'a']++; } int p_len=p.length(); int left=0,right=0; while(right<s.length()){ arr[s.charAt(right)-'a']--; if (arr[s.charAt(right)-'a']>=0) p_len--; if(p_len==0) list.add(left); //维护窗口大小 if(right-left==p.length()-1){ if(arr[s.charAt(left)-'a']>=0) p_len++; //恢复 arr[s.charAt(left)-'a']++; left++; } right++; } return list; } }
3.76. 最小覆盖子串
给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。
示例：
输入: S = "ADOBECODEBANC", T = "ABC" 输出: "BANC"
说明：
- 如果 S 中不存这样的子串，则返回空字符串
""。 - 如果 S 中存在这样的子串，我们保证它是唯一的答案。
实现思路：
首先让右指针不断往前走,左指针不动,直到将窗口拉到最大,同时包含t中所有字符串。
定义一个HashMap,key为character,value为Integer。先循环t字符串长度，这个HashMap中保存了t中所有字符。key为t中字符，value为t中字符出现的次数。
然后定义左右指针，left与right，当s中的right对应的元素在HashMap中，就让对应的value减1，每减1，也就是与t中匹配的字符串就得减去1，也就是t_len减去1。当t_len为0，表示right已经拉到最大，此时窗口包含所有t中元素，就要移动left，进而压缩窗口大小，使得找出最小覆盖子串。
实现：
class Solution { public static String minWindow(String s, String t) { HashMap<Character, Integer> hashMap = new HashMap<>(); if (s == null || t == null || s.length() < t.length()) return ""; for (int i = 0; i < t.length(); i++) { if(hashMap.get(t.charAt(i))!=null){ hashMap.put(t.charAt(i), hashMap.get(t.charAt(i)) + 1); }else{ hashMap.put(t.charAt(i), 1); } } int t_len = t.length(); int left = 0, right = 0; int minlen = s.length() + 1; int minleft=0; while (right < s.length()) { if (hashMap.containsKey(s.charAt(right))) { Integer in = hashMap.get(s.charAt(right)); in--; hashMap.remove(s.charAt(right)); hashMap.put(s.charAt(right),in); if (in >= 0) t_len--; //表示t中此时被访问过的元素-1 } //窗口拉到了最大，寻找匹配，看是否是最小长度子串。 while(t_len == 0){ if(right - left + 1 < minlen){ minlen = right - left + 1; minleft = left; } //左边的元素如果在hashMap中，那么就要恢复原来的值，因为左边的值必定被右边right访问过，而right访问的时候只要在hashMap中，就会减去1，所以这里要恢复，也就是+1，同是如果此时恢复过后的值>0就需要，让t_len+1。表示t中此时没被访问过的元素+1。 if (hashMap.containsKey(s.charAt(left))) { Integer lt = hashMap.get(s.charAt(left)); lt++; if(lt>0){ t_len++; } hashMap.remove(s.charAt(left)); hashMap.put(s.charAt(left),lt); } left++; } right++; } if(minlen==s.length()+1){ return ""; } return s.substring(minleft, minleft + minlen); } }
上述精简版:
class Solution { public static String minWindow(String s, String t) { HashMap<Character, Integer> hashMap = new HashMap<>(); if (s == null || t == null || s.length() < t.length()) return ""; for (int i = 0; i < t.length(); i++) { if(hashMap.get(t.charAt(i))!=null){ hashMap.put(t.charAt(i), hashMap.get(t.charAt(i)) + 1); }else{ hashMap.put(t.charAt(i), 1); } } int t_len = t.length(); int left = 0, right = 0; int minlen = s.length()+1,minleft=0; while (right < s.length()) { if (hashMap.containsKey(s.charAt(right))) { int rt = hashMap.getOrDefault(s.charAt(right), 0); rt--; hashMap.put(s.charAt(right), rt); if (rt >= 0) t_len--; } while(t_len == 0){ if(right - left + 1 < minlen){ minlen = right - left + 1; minleft = left; } if (hashMap.containsKey(s.charAt(left))) { int lt = hashMap.getOrDefault(s.charAt(left), 0); lt++; if(lt>0){ t_len++; } hashMap.put(s.charAt(left), lt); } left++; } right++; } return (minlen == s.length() + 1) ? "" : s.substring(minleft, minleft + minlen); } }
总结：第3题与第2题特别相似，都是先确定一个窗口，然后不断调整左右窗口范围，需要注意不同点：第2道题是让t串的字符串出现在s中并且连续，所以滑动窗口的长度在第一次确定后就可以不变了。而第3道题则是先确定一个包含所有字符串t的窗口，不断压缩这个最大窗口，然后再继续移动左右指针。
