leetcode76

Question

class Solution {
public String minWindow(String s, String t) {
int[] tFreq = new int[256];
for (int i = 0; i < t.length(); i++) {
tFreq[t.charAt(i)]++;
}

        int[] sFreq = new int[256];
        // [l,r] 滑动窗口
        // 目标找出最短的 r - l + 1
        int l = 0;
        int r = -1;
        String res = "";
        int min = Integer.MAX_VALUE;
        while (r + 1 < s.length()) {
            r++;
            sFreq[s.charAt(r)]++;
            while (r - l + 1 >= t.length() && contains(sFreq, tFreq)) {
                if (r - l + 1 < min) {
                    min = r - l + 1;
                    res = s.substring(l, r + 1);
                }
                sFreq[s.charAt(l)]--;
                l++;
            }
        }
        return res;
    }

    private boolean contains(int[] sFreq, int[] tFreq) {
        for (int i = 0; i < sFreq.length; i++) {
            if (sFreq[i] < tFreq[i]) {
                return false;
            }
        }

        return true;
    }
}

波波老师，根据你438的解法，我理解后，模仿着把76题给解决，提交是通过的，可是时间效率不是很高，想请教下是接着往下呢，还是咋弄，是这样的，我现在处于离职状态，打算复习下之后找工作，我现在是尽可能通过这些练习题即可，还是也去找下最优解法，尽可能去理解

Answer 1

liuyubobobo 2023-08-21 15:40:48

整体算法思路没有问题，两个小优化，如下代码所示：

1）每次找到 r - l + 1 < min 的时候，没必要求一下 res 的子串，记录这个 l 和 r 即可，最后求一次子串即可。

2）因为字符串中只有大写字母和小写字符，所以 contains 中没必要遍历 256 个字符，遍历 52 个字符即可（26 个大写字母和 26 个小写字母）

class Solution {
    public String minWindow(String s, String t) {
        int[] tFreq = new int[256];
        for (int i = 0; i < t.length(); i++) {
            tFreq[t.charAt(i)]++;
        }
        int[] sFreq = new int[256];
        
        // [l,r] 滑动窗口
        // 目标找出最短的 r - l + 1
        int l = 0, r = -1;
        int resl = -1, resr = -1; 
        int min = Integer.MAX_VALUE;
        while (r + 1 < s.length()) {
            r++;
            sFreq[s.charAt(r)]++;
            while (r - l + 1 >= t.length() && contains(sFreq, tFreq)) {
                if (r - l + 1 < min) {
                    min = r - l + 1;
                    resl = l; resr = r; // 1)
                }
                sFreq[s.charAt(l)]--;
                l++;
            }
        }
        return resl == -1 ? "" : s.substring(resl, resr + 1);
    }
    
    private boolean contains(int[] sFreq, int[] tFreq) {
    
        // 2)
        for (int i = 0; i < 26; i++) {
            if (sFreq['a' + i] < tFreq['a' + i] || sFreq['A' + i] < tFreq['A' + i]) {
                return false;
            }
        }
        return true;
    }
}

==========

关于练习的个人建议：

1)

对于一个问题，如果有更优复杂度的算法解法，应该去搞明白。否则，同等复杂度的情况下，对于具体实现上的细节，不需要太深究，ac 即可。（对于这个问题，我给出的两个优化，不属于复杂度级别的优化，不需要深究。）

2）

力扣上的效率百分比是不准的。因为不同的时间里，里扣的测试用例数量，编译器的版本，服务器的性能，都是不同的，所以不要以那个百分比作为依据。依然是：如果一个问题，已经没有更优复杂度的解法了，就不需要深究了。（甚至对于一些问题，即使有更有复杂度的解法，也不需要深究。比如”马拉车“算法，以面试为导向，完全没必要学习。）

继续加油！：）