【題目描述】

創(chuàng)新互聯(lián)專注于企業(yè)成都全網(wǎng)營銷推廣、網(wǎng)站重做改版、瑪納斯網(wǎng)站定制設(shè)計、自適應(yīng)品牌網(wǎng)站建設(shè)、H5響應(yīng)式網(wǎng)站、商城系統(tǒng)網(wǎng)站開發(fā)、集團公司官網(wǎng)建設(shè)、成都外貿(mào)網(wǎng)站建設(shè)公司、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計等建站業(yè)務(wù)，價格優(yōu)惠性價比高，為瑪納斯等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。

Given a string source and a string target, find the minimum window in source which will contain all the characters in target.

Notice:If there is no such window in source that covers all characters in target, return the emtpy string "".If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in source.

給定一個字符串source和一個目標字符串target，在字符串source中找到包括所有目標字符串字母的子串。

注意:如果在source中沒有這樣的子串，返回""，如果有多個這樣的子串，返回起始位置最小的子串。

【題目鏈接】

http://www.lintcode.com/en/problem/minimum-window-substring/

【題目解析】

可以用窗口型兩個指針的思路來解決，外層for循環(huán)i = 0 ... n, 內(nèi)層while循環(huán)，條件是j < source.length() 和 !isValid(sourceHash, targetHash)，前者是數(shù)組下標邊界，后者是一個函數(shù)，檢查當前窗口中的substring是否包含了目標字符串中全部所需的字符，未滿足則繼續(xù)擴大窗口j++，同時更新sourceHash。這里sourceHash，targetHash是整型數(shù)組int[]，因為ASCII碼最多256個，因此用int[]可以作為簡化的HashMap使用，key是char對應(yīng)的int的值，value則是該char在substring中的出現(xiàn)個數(shù)。isValid函數(shù)則檢查sourceHash是否全部包含了targetHash，256個字符一一對應(yīng)，因此只需一重for循環(huán)，如果sourceHash[i] < targetHash[i]，則說明有字符未滿足條件。

需要注意的是，要設(shè)定一個輔助變量記錄minStr的長度。

【參考答案】

http://www.jiuzhang.com/solutions/minimum-window-substring/