leetcode438求解过程有一个问题
来源：3-8 在滑动窗口中做记录 Longest Substring Without Repeating Characters
envy
2017-06-21
public class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res =new ArrayList<>();
if (s == null || s.length() == 0 || p == null || p.length() == 0){
return res;
}
int[] chars = new int[256];
for(Character c:p.toCharArray()){
chars[c]++;
}
int count = p.length(),left = 0,right = 0;
while(right < s.length()){
if (chars[s.charAt(right)] >= 1){
count--;
}
chars[s.charAt(right)]--;
right++;
if (count == 0){
res.add(left);
}
if (right - left == p.length()){
//这面这一行为什么将大于等于换成==就报错了，之前right经过的每个点应该都被减一了，那么这些
//点不是0就是-1，这里判断包含的点所以也就是值为0点，需要count++，那直接把判断条件改成==
//应该就对啦，为什么不对呢，相同的改法我在第76题上实验就是正确的。
if (chars[s.charAt(left)] >= 0){
count++;
}
chars[s.charAt(left)]++;
left++;
}
}
return res;
}
}下面是76题的代码：
public class Solution {
public String minWindow(String s, String t) {
char[] s_array = s.toCharArray();
char[] t_array = t.toCharArray();
int[] chars = new int[256];
int end = 0;
int start = 0;
int min_length = Integer.MAX_VALUE;
for (Character c:t_array){
chars[c]++;
}
int count = t_array.length;
int min_start = 0;
while(end < s_array.length){
if (chars[s_array[end]] > 0){
count--;
}
chars[s_array[end]]--;
while(count == 0){
if (end - start +1 <min_length){
min_length = end - start +1;
min_start = start;
}
//这里我将判断条件改为==依然成立，大于等于也成立
if (chars[s_array[start]] == 0){
count++;
}
chars[s_array[start]]++;
start++;
}
end++;
}
if (min_length+min_start > s_array.length)
return "";
return s.substring(min_start,min_length+min_start);
}
}1回答
-
liuyubobobo
2017-06-21
在你的程序中，count表示p中还有多少个字符，没有包含在s[left,right)这个窗口范围里。（所以 count == 0 时判断找到了一个解，表示p中的所有字符被包含在了窗口中。）
chars这个数组表示针对某一个具体字符，当前窗口和目标字符串的差异是多少。chars[c]记录了当前窗口s[left,right)和目标字符串p中，针对字符c的差异:
如果 chars[c] == 0，表示两个字符串对于字符c的数量无差异；
如果 chars[c] > 0 表示当前窗口中缺少chars[c]个字符c；
如果 chars[c] < 0 表示当前窗口中富裕了chars[c]个字符c。
在你的程序的第29行，其实是在left做加1操作之前，判断一下当前所看的窗口左边界向右移动一位时，count是否需要调整。我们依然分情况讨论：
如果 chars[c] == 0，说明当前两个字符串对于字符c的数量无差异，但是left++后，这个字符c在窗口里少了一个，所以count应该++；
如果 chars[c] > 0 表示窗口中缺少chars[c]个字符c; left++后，这个字符c在窗口里更少了，所以count应该++；
如果 chars[c] < 0 表示窗口中富裕了chars[c]个字符c; left++后，这个字符c在窗口里少了，就是少富裕了一个。但根据count的定义，这种情况不影响count值。在你定义的count语意下，可以不维护count。（注意，我们如果换一个count的语意，在这里就要维护count，但相应的在其他地方也要做维护。这是一个很有意思的例子。）
所以，你可以看出来，在chars[c] >= 0 时，count都要++。
如下测试用例是一个反例，说明改成==0，逻辑是有误的。有兴趣的话，你可以调试跟踪一下，加深理解。
s = “aabaab" p = “aa"
同样的思路可以用于76题。但是要注意：76题和438不一样！438要求窗口中的字母和目标字符串中的字母完全一致！但是76题中，窗口中的字母包含目标字符串中的全部字母即可。也就是窗口中的字母数量可以多于目标字符串中的字母数量。所以，在两个问题中，你移动左边界的条件是不一样的。在438中，你移动左边界的条件是 right - left == p.length()，也就是窗口长度要固定，此时count可能不为0，也就是存在目标字符串中还有字符没有被窗口包含的情况。但是在76题中，移动左边界的条件为：count == 0。换句话说，此时，目标字符串中的所有字符肯定已经包含在了窗口中。所以，在76中，你的25行程序，chars[s_array[start]] 是不可能大于0的。虽然我认为从维护语意的角度讲，写成>=0更清晰。但是从逻辑的角度讲，由于不可能>0，所以写==0是没有错的。
132017-06-22
相似问题
回答 1
回答 1