#438号题疑问

Question

// JS相关实现
/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    var needMap = {}; // 实际需要的hashMap

    for(var i = 0; i < p.length; i++) {
        needMap[p[i]] ? needMap[p[i]]++ : needMap[p[i]] = 1;
    }

    var needLen = Object.keys(needMap).length;

    var realMap = {}; // 窗口的hashmap
    var res = [];

    var l = 0, r = 0;
    var matchCount = 0; // 匹配到的字母总个数

    while(r < s.length) {
        var cur = s[r];
		
		// 当前元素 是 需要的元素
        if(needMap[cur]) {
	        // 窗口map 计数
            realMap[cur] ? realMap[cur]++ : (realMap[cur] = 1);
            // 如果数量相等了，匹配到的个数就 +1
            if(needMap[cur] === realMap[cur]) {
                matchCount++;
            }
        }

        r++;

        while(matchCount === needLen) {
            var leftItem = s[l];
            if((r - l) === p.length) {
                res.push(l);
            }
            if(needMap[leftItem] && realMap[leftItem]) {
                realMap[leftItem]--;
                if(realMap[leftItem] < needMap[leftItem]) {
                    matchCount--;
                }
            }
            l++;
        }
    }

    return res;
};

老师，关于这题我有个疑问，我们在记录窗口中的字母个数时， 遇到是我们需要的字母 就会计数， 那如果碰到了 其他字母 却没有重置map， 是因为 我们这里考虑的子串 是 不一定要连续的吗？ 在官方题目描述上没有看到关于这块的描述。

Answer 1

liuyubobobo 2021-01-04 16:20:31

考虑的子串是连续的。正是因为没有重置，整个算法才能是线性的。

if((r - l) === p.length) 这个判断，保证了不仅仅在这个子串中，所有的字母都出现了，而且肯定没有多余的字符。

设想一个你认为可能出问题的测试用例，比如存在一个不连续的子串，除了给定的字符，还有多余字符，运行你的程序，看一看是否会出问题？如果没有出问题，单步跟踪一下，看看这个程序为什么能躲过你设想的问题？

进步就在这个过程中哦。

继续加油！：）

• 提问者 慕粉4283821 #1

  感谢老师，我好像懂了。 通过上面的判断保证子串是连续的，如果长度没有满足，会通过后面的逻辑 将 窗口左边界右移，在右移的过程中会移除掉 不满足条件的字符