?LeetCode3给定一个字符串s,请你找出其中不含有重复字符的最长子串的长度。例如:
输入:s="abcabcbb"
输出:3
解释:因为无重复字符的最长子串是"abc",所以其长度为3。
?要找最长子串,必然要知道无重复字符串的首和尾,然后再从中确定最长的那个,因此至少两个指针才可以,这就想到了滑动窗口思想。
?定义一个K-V形式的map,key表示的是当前正在访问的字符串,value,是其下标索引值。我们每访问一个新元素,都将其下标更新成对应的索引值。具体过程如下图:
?如果是已经出现过的,例如上述示例中的abcabc,当第二次遇到a时,我们就更新left成为第一个b所在的位置,此时发现left要移动的位置恰好就是map.get(‘a’)+1=1,将’a’用序列来表示,放在一起就是map.get(s.charAt(i)+1。其他情况可以参考图示依次类推。
?有一种特殊情况是需要考虑的,例如abba,我们第二次访问b时, left=map.get('b)+1=2。然后继续访问第二个a,此时left=map.get('a‘)+1=1,也就是left后退了,显然不对。
?我们应该让t在2的基础上继续向前,那该怎么办呢?和原来的对比一下,将最大的加1就可以了,也就是:left=Math.max(left,map.get(s.charAt(i))+1);
完整的代码如下:
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(),max = 0;
Map<Character, Integer> map = new HashMap<>();
for(int end = 0, start = 0; end < n; end++){
char element = s.charAt(end);
if(map.containsKey(element)){
start = Math.max(map.get(element)+1, start);
}
max = Math.max(max, end - start + 1);
map.put(element, end);
}
return max;
}
}
?LeetCode159题 给定一个字符串S,找出至多包含两个不同字符的最长子串t,并返回该子串的长度。例如:
输入:"eceba"
输出:3
解释:t是"ece",长度为3。
?我们仍然使用Ieft和ight来锁定一个窗口,然后一边向右移动一边分析。我们用一个序列来看一下:aabbcccd。
?我们接下来需要解决两个问题,一个是怎么判断只有2个元素,另一个是移除的时候怎么知道移除谁,以及移除之后left是什么。
?要判断只有2个元素,还是Hash好用,每一个时刻,这个hashmap包括不超过3个元素。这里还要考虑到要移除谁,所以我们要设计一下Hash的Key-Valuet的含义。我们把字符串里的字符都当做键,在窗口中的最右边的字符位置作为值。此时使用下面的代码就可以确定要删除谁,以及窗口left的新位置:
//伪码,从Hash中找最小值
del_idx = Collections.min(hashmap.values());
left = del_idx + 1;
public int lengthofLongestSubstringTwoDistinct(String s){
if(s.length() < 3){
return s.length();
}
int left = 0, right = 0;
HashMap<Character,Integer> hashmap = new HashMap();
int maxLen = 2;
while(right < s.length()){
if(hashmap.size() < 3)
hashmap.put(s.charAt(right),right++);
//如果大小达到了3个
if(hashmap.size()==3){
//最左侧要删除的位置
int del_idx = Collections.min(hashmap.values());
hashmap.remove(s.charAt(delidx));
//窗口left的新位置
left = del_idx + 1;
}
maxLen = Math.max(maxLen, right -left);
}
return maxLen;
}
?如果再提高一下难度,至多包含K个不同字符的最长子串该怎么办呢?这是LeetCode340题。题目的完整要求是:给定一个字符串S,找出至多包含k个不同字符的最长子串T。示例:
输入:S="eceba",k=2
输出:3
解释:则T为"ece",所以长度为3。
?本题与上面的题几乎没有区别,只要将判断hash大小为2改成k就可以,超过2就是k+1。十分钟实现:
public int lengthofLongestSubstringTwoDistinct(String s, int k){
if(s.length() < k + 1){
return s.length();
}
int left = 0, right = 0;
HashMap<Character,Integer> hashmap = new HashMap();
int maxLen = k;
while(right < s.length()){
if(hashmap.size() < k + 1)
hashmap.put(s.charAt(right),right++);
//如果大小达到了k+1个
if(hashmap.size()== k + 1){
//最左侧要删除的位置
int del_idx = Collections.min(hashmap.values());
hashmap.remove(s.charAt(delidx));
//窗口left的新位置
left = del_idx + 1;
}
maxLen = Math.max(maxLen, right -left);
}
return maxLen;
}
?LeetCode209.长度最小的子数组,给定一个含有n个正整数的数组和一个正整数target。找出该数组中满足其和≥target的长度最小的连续子数组[numsl,numsl±1,numsr-1,numsr],并返回其长度。如果不存在符合条件的子数组,返回0。
输入:target=7,nums=[2,3,1,2,4,3]
输出:2
解释:子数组[4,3]是该条件下的长度最小的子数组。
?本题可以使用双指针来解决,也可以视为队列法,基本思路是先让元素不断入队,当入队元素和等于target时就记录一下此时队列的容量,如果队列元素之和大于target则开始出队,直到小于target则再入队。
?如果出现等于target的情况,则记录一下此时队列的大小,之后继续先入队再出队。每当出现元素之和等于target时我们就保留容量最小的那个。
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0, right = 0;
int sum = 0;
int min = nums.length + 1;
for(right = 0; right < nums.length; right++){
sum+= nums[right];
if(sum >= target){
for(;left < right; left++){
if(sum - nums[left]>= target) sum -= nums[left];
else break;
}
min = Math.min(min, right - left + 1);
}
}
return min == nums.length + 1? 0 : min;
}
}
?LeetCode11.给定一个长度为n的整数数组height。有n条垂线,第i条线的两个端点是(i,0)和(i,height[i])。找出其中的两条线,使得它们与×轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
平平无奇双指针,下面自己的解法
class Solution {
public int maxArea(int[] height) {
int left = 0,right = height.length-1; //创建左右指针,分别指向数组的开端和末端
int max = 0; //max用于记录最大值
while(left < right){ //当左右指针还未重合时
int v = (right - left) * Math.min(height[left] , height[right]); //计算当前的容水量
max = max > v ? max : v; //利用三目运算符判断最大值是否需要改变
if(height[left] < height[right]) left++; //对指向 高度比较低 的指针进行移动
else right--;
}
return max; //返回最大值
}
}
讲义解法,压缩版
public int maxArea(int[] height){
int i=0,j=height.length -1,res 0;
while(i<j){
res = height[i] < height[j] ?
Math.max(res,(j-i)*height[i++]):
Math.max(res,(j-i)height [j--]);
}
return res;
}
?LeetCode567.给你两个字符串s1和s2,写一个函数来判断s2是否包含s1的排列。如果是,返回true;否则,返回flse。换句话说,s1的排列之一是s2的子串。其中s1和s2都只包含小写字母。
示例:
输入:s1="ab"s2="eidba00o"
输出:true
解释:s2包含s1的排列之一("ba").
public boolean checkInclusion(String s1, String s2) {
if(s1.length() > s2.length()) return false;
int[] arr1 = new int[26];
int[] arr2 = new int[26];
for(int i = 0; i < s1.length(); i++){
arr1[s1.charAt(i) - 'a']++;
arr2[s2.charAt(i) - 'a']++;
}
if(Arrays.equals(arr1,arr2)) return true;
int j = 0;
for(int i = s1.length(); i < s2.length(); i++){
arr2[s2.charAt(i) - 'a']++;
arr2[s2.charAt(j) - 'a']--;
j++;
if(Arrays.equals(arr1,arr2)) return true;
}
return false;
}
}
?LeetCode438.找到字符串中所有字母异位词,给定两个字符串s和p,找到s中所有p的异位词的子串,返回这些子串的起始索引。不考虑答案输出的顺序。注意s和ρ仅包含小写字母。异位词指由相同字母重排列形成的字符串(包括相同的字符串)。
例如:
输入:s="cbaebabacd",p="abc"
输出:[0,6]
解释:
起始索引等于0的子串是
"cba",它是"abc"的异位词。
起始索引等于6的子串是"bac",它是"abc"的异位词。
?本题的思路和实现与上面几乎一模一样,唯一不同的是需要用一个List,如果出现异位词,还要记录其开始位置,那直接将其add到List中就可以了。完整代码:
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> list = new ArrayList();
if(s.length() < p.length()) return list;
int[] arr1 = new int[26]; //保存p
int[] arr2 = new int[26]; //保存s
for(int i = 0; i < p.length(); i++){
arr1[p.charAt(i) - 'a']++;
arr2[s.charAt(i) - 'a']++;
}
if(Arrays.equals(arr1,arr2)) list.add(0);
int left = 0;
for(int right = p.length(); right < s.length(); right++){
arr2[s.charAt(right) - 'a']++;
arr2[s.charAt(left) - 'a']--;
left++;
if(Arrays.equals(arr1,arr2)) list.add(left);
}
return list;
}
}