数组刷题<下>套路分析
数组刷题<下>套路分析
数组刷题<下>套路分析
一、双索引技术-对撞指针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的窗口，不断压缩这个最大窗口，然后再继续移动左右指针。