Leetcode——76. 最小覆寫子串

概述

題目連接配接

• 注意：要求時間複雜度為 O ( n ) O(n) O(n)

分析

要求 O ( n ) O(n) O(n)，并且結果也是一個連續的字元串，是以考慮使用雙指針進行區間搜尋

思路

• 滑動視窗思路？
  • 首先固定左邊界，然後右邊界開始向右滑動向視窗中加入元素
  • 當所有所需的字元加入視窗後，此時右邊界是最小的，但是左邊界不一定，是以可以移動左邊界，将字元移出去的同時繼續使視窗滿足條件
  • 直到因為左邊界移動導緻該視窗不滿足條件，則停止移動左邊界，繼續移動右邊界
  • 重複以上行為，直到右邊界到達最後位置

代碼

class Solution {
public:
    string minWindow(string s, string t) {
        // 前置處理，用來判斷視窗内是否包含所有字元
        unordered_map<char,int> unordered_map_char_to_int;
        for (auto p : t) 
            ++unordered_map_char_to_int[p];
    
        int size_s = s.size(), size_t = t.size();
        int l = 0;			// 記錄目前視窗的左邊位置
        int min_l = 0;		// 記錄之前視窗的左邊位置
        int min_size = size_s + 1;        	// 記錄視窗大小
        int count = 0;          			// 記錄是否包含所有字元
        // 視窗左邊界不動，右邊界滑動，直到包含所有所需字元後，再移動左邊界目的是減小視窗
        for(int r = 0; r < size_s; ++r) {
            if (unordered_map_char_to_int[s[r]]-- > 0) {		// >0，說明t中的字元被包含 
                ++count;
                while (count == size_t) {       	// 視窗内包含t的所有字元
                    if (r - l + 1 < min_size) {		// 比較視窗大小
                        min_l = l;		// 記錄新視窗
                        min_size = r - l + 1;
                    }
                    if (++unordered_map_char_to_int[s[l]] > 0) {	// 移動視窗
                        											// 注意大小判斷: >0說明所需某個字元已經不存在視窗中，此時需要右側開始移動
                        --count;										
                    }
                    ++l;	// 移動現在視窗左邊界，盡可能減小視窗
                }
            }
        }
        return min_size > size_s ? "" : s.substr(min_l, min_size);
    }
};
           

• 盡管

  for

  循環裡面有

  while

  循環，但是最壞情況是 O ( 2 n ) O(2n) O(2n)