題目

解答

想到使用雙指針+哈希表來實現，雙指針的left和right控制實現可滿足字符串。

class Solution(object):def minWindow(self, s, t):""":type s: str:type t: str:rtype: str"""len_s, len_t = len(s), len(t)hash_map = {}for i in range(len_t):if t[i] in hash_map:hash_map[t[i]] += 1else:hash_map.setdefault(t[i], 1)copy_hash = deepcopy(hash_map)min_len = 1e5min_left = 0tag = False # 記錄是否已經找到滿足條件子串for left in range(len_s):if s[left] not in hash_map:continueright = leftwhile len(copy_hash) != 0 and right < len_s:if s[right] in copy_hash:if copy_hash[s[right]] > 1:copy_hash[s[right]] -= 1elif copy_hash[s[right]] == 1:copy_hash.pop(s[right])right += 1if len(copy_hash) != 0: #代表right >= len_sbreakelse: # 代表找到一個合法塊滿足要求tag = Truecurrent_len = right - leftif current_len < min_len:min_len = current_lenmin_left = leftcopy_hash = deepcopy(hash_map)if tag == True:return s[int(min_left):int(min_left+min_len)]else:return ""

報錯：

仔細看了代碼，發現我使用的雙指針會造成平方復雜度，每次左指針移動后，都重新從當前的left位置開始擴展右指針，這樣會有大量的重復計算。所以，需要重新設計算法，使用更高效的滑動窗口方法。可能的改進方向是：維護一個滑動窗口，用兩個指針left和right。先擴展right直到窗口包含所有t的字符，然后嘗試移動left縮小窗口，同時更新最小窗口的長度。這樣每個元素最多被訪問兩次（left和right各一次），時間復雜度為O(n)。另外，原來的代碼中使用了deepcopy來恢復copy_hash，這可能也很耗時。因為每次循環都要復制整個哈希表，當哈希表較大時，這會增加時間消耗。應該維護一個當前的計數器，動態地增減字符出現的次數，而不是每次都復制哈希表。

修改后的代碼如下：

class Solution(object):def minWindow(self, s, t):""":type s: str:type t: str:rtype: str"""# 構造哈希表-tmap_t = defaultdict(int)for st in t:map_t[st] += 1# 需要符合條件的字符數require_len = len(map_t)current_window = defaultdict(int)try_len = 0left = 0min_len = 1e5min_left = 0tag = Falsefor right in range(len(s)):current_window[s[right]] += 1if s[right] in map_t and current_window[s[right]] == map_t[s[right]]:try_len += 1while try_len == require_len and left <= right:tag = Truecurrent_len = right - left + 1if current_len < min_len:min_len = current_lenmin_left = leftcurrent_window[s[left]] -= 1if s[left] in map_t and current_window[s[left]] < map_t[s[left]]:try_len -= 1left += 1if tag == True:return s[min_left: min_left + min_len]else:return ""