Leetcode刷題學習筆記 – Sliding Window

Introduction

sliding window 定義

  • right定義為sliding window裡面的最右邊。
  • left定義為sliding window裡面的最左邊。
  • 根據上面的定義，slding window的長度為 right - left + 1

left前進條件

結束條件

通常會有兩種結束條件的寫法。






// 當left == right, 則length = right - right + 1 = 1
// 也就是window最小長度為1，至少會有一個element在window中。
while(left <= right) {
    
}

另一種結束條件






// 當left == right + 1, 則length = right - right - 1 + 1 = 0
// 也就是window最小長度為0，window可以為empty。
while(left <= right + 1) {
    
}

關於結束條件，可以參考lee215的解說

Code snippet








for(int left = 0, right = 0; right < size; ++right) {
    ++m[s[right]]; // 把right加入到window中
    while(left <= right + 1 && other_condition) {
        
        --m[s[left++]]; // 把left從window中移除
    }
}

Time Complexity

  • time complexity is linear, so it is \(O(N)\)

Problems

3. Longest Substring Without Repeating Characters(Medium)

找出最長的substring(連續的字元)，裡面沒有重複的char。

  1. 因為要統計沒有重複的字元，且要記錄index所以使用map。
  2. left為substring的前一個，而不是substring的第一個。
















int lengthOfLongestSubstring(string s) {
    unordered_map<int, int> m;
    auto n = s.length();   
    int left{-1}, rtn{0};
    
    for(int i = 0; i < n; ++i) {
        /* 重複，且比left還後面*/
        if(m.count(s[i]) && m[s[i]] > left)
                left = m[s[i]];
              
        m[s[i]] = i;
        //　每次都update結果，避免最後還需要判斷一次。
        rtn = max(rtn, i - left);
    }    
    return rtn;
}

2022/06/10

本來是使用sliding windows的概念。但是遇到重複的char的時候，left只能一個一個往前進，比較沒效率。最好的方法是直接跳到重複出現char的下一個位置。因為"abca"已經計算過abc，大小和bca一樣，所以直接跳到a的下一個位置。















int lengthOfLongestSubstring(string s) {
    int sz = s.length();
    if(sz <= 1) return sz;
    int left = 0, right = 0, maxans = 0;
    vector<int> alpha(256);
    while(right < sz) {
        if(alpha[s[right]])
            alpha[s[left++]]--;
        else
            alpha[s[right++]]++;
        maxans = max(maxans, right - left);
    }
    return maxans;
}
















int lengthOfLongestSubstring(string s) {
    int sz = s.length();
    // special case, don't need judge
    if(sz <= 1) return sz;
    vector<int> dict(256, -1);
    dict[s[0]] = 0;
    int left = 0, maxans = 1;
    for(int right = 1; right < sz; ++right) {
        if(dict[s[right]] >= left) // 在left的右邊出現過重複的char
            left = dict[s[right]] + 1;
        dict[s[right]] = right;
        maxans = max(maxans, right - left + 1);
    }
    return maxans;
}

time complexity : \(O(N)\) 因為只需要走訪一次string
space complexity : \(O(1)\) 因為只需要一個固定256的vector來儲存char和idx的對應。

567. Permutation in String(Medium)

有兩個字串s1和s2，找出s2中是否有s1的排列。

  1. 使用vector統計s1中，所有出現的alphabet的數量。
  2. 統計s2中和s1相同長度的alphabet數量。
  3. vector長度一樣，則==會比較每個元素的大小是否一樣。



















bool checkInclusion(string s1, string s2) {
    vector<int> m1(26, 0), m2(26, 0);
    auto n1 = s1.length();
    auto n2 = s2.length();
    if(n1 > n2) return false;
    for(int i = 0; i < n1; ++i) {
        m1[s1[i]-'a']++;
        m2[s2[i]-'a']++;
    }
        
    if(m1 == m2) return true;
    for(int i = n1; i < n2; ++i) {
        m2[s2[i]-'a']++;
        m2[s2[i - n1]-'a']--;
        if(m1 == m2) return true;
    }
        
    return false;
}

713. Subarray Product Less Than K(Medium)

給你一個vector<int>，找出subarray的相乘數字小於K。返回subarray的數量。

  1. subarray表示是連續的element，所以可以使用slide window。用left表示subarray的下標，用right表示subarray的上標。
  2. right做到哪，就可以得出subarray的數量。所以time complexity為O(N)。
  3. 當prod >= K，則left必須往前進，直到prod < K，所以使用while。
  4. 當3在判斷的時候須注意，left < right這個條件。












int numSubarrayProductLessThanK(vector<int>& nums, int k) {
    if(k == 0) return 0;
    int rtn{0}, left{0}, right{0}, prod{1};
    while(right < nums.size()) {
        prod *= nums[right++];
        while(left < right && prod >= k)
                prod /= nums[left++];
            
        rtn += right - left;
    }
    return rtn;
}

209. Minimum Size Subarray Sum(Medium)

給定一個vector<int>，subarray中相加值大於等於target，返回最小的subarray長度。

  1. 思考方式和713一樣，因為是subarray所以可以用slide window來思考。
  2. 當sum(subarray) >= target之後，馬上紀錄是否為最小長度。
  3. 然後left一直往前移動，直到sum(subarray) < target為止。












int minSubArrayLen(int target, vector<int>& nums) {
    auto n = nums.size();
    int left{0}, right{0}, rtn{INT_MAX}, sum{0};
    while(right < n) {
        sum += nums[right++]; 
        while(left < right && sum >= target) {
            rtn = min(rtn, right - left);
            sum -= nums[left++];
        }
    } 
    return rtn == INT_MAX ? 0 : rtn;
}

487. Max Consecutive Ones II

找出最多的連續1，最多可以翻轉一次0成1。

int findMaxConsecutiveOnes(vector<int>& nums) {
    int sz = nums.size();
    int left = 0, rtn = 0, zeros = 0, k = 1;
    for(int right = 0; right < sz; ++right) {
        if(nums[right] == 0) ++zeros;
        while(zeros > k) {
            if(nums[left++] == 0) --zeros;
        }
        rtn = max(rtn, right - left + 1);
    }
    return rtn;
}

424. Longest Repeating Character Replacement

給你一個字串，允許你修改k個char，找出最長的連續重複字串。

  1. 一開始想到就是用slinding window來計算。
  2. 假設一個window中由最大出現頻率的char和其他所組成，那修改其他char就會得到最長的Repeating char string。
  3. 根據上面的假設，
    maxf + others = total
    total - maxf = others <= k
    因為剩下的char不能大於k
  4. 為什麼不用更新maxf ?
    當找到一個答案的時候，如果有下一個比目前答案還要長的字串，勢必新的maxf一定會大於之前的。
  5. total也可以用right - left + 1來取代。



















int characterReplacement(string s, int k) {
    int maxans = 0, maxf = 0;
    int left = 0, total = 0;
    int sz = s.size();
    vector<int> st(26);
    for(int right = 0; right < sz; ++right) {
        maxf = max(maxf, ++st[s[right] - 'A']);
        total++;
        if(total - maxf <= k)
            maxans = max(maxans, right - left + 1);
        else {
            --st[s[left++] - 'A'];
            total--;
        }
    }
    // time  : O(N)
    // space : O(1)
    return maxans;
}

1712. Ways to Split Array Into Three Subarrays

給你一個vector<int> nums, 我要把vector分成三個subarray。且必須滿足 1st subarray sum <= 2nd subarray sum。2nd subarray sum <= 3rd subarray sum。滿足這樣的條件的subarray切法有幾種?

  1. 因為是求subarray sum所以使用prefix sum
  2. i : 代表1st subarray的右邊界，因為subarray不能為空，所以 i<= sz - 3;
  3. j : 代表2nd subaary的右邊界，且滿足1st sum <= 2nd sum
  4. k : 代表2nd subaary的右邊界，且不滿足2nd sum <= 3rd sum。
  5. 使用 j = max(j, i + 1) 是因為j 不用從i + 1開始找，從上次j繼續往後找。
class Solution {
    // 1, 2, 2, 2,  5,  0
    // 1, 3, 5, 7, 12, 12
    //    i        j/k
    // <-->  <------>  <-->   // j, k是second subarray的右邊界範圍
    //   j/k <= sz - 2
    //   i <= sz - 3
    // pfs[i] --> first subarray sum, j the last index of first array
    // pfs[j/k] - pfs[i] --> second subarray sum, k the last index of first array
    // pfs[sz - 1] - pfs[j/k] -- > third subarray sum
public:
    int waysToSplit(vector<int>& nums) {
        int sz = nums.size();
        partial_sum(nums.begin(), nums.end(), nums.begin());
        int rtn{0}, mod = 1e9 + 7;
        for(int i = 0, j = 0, k = 0; i <= sz - 3; ++i) {
            j = max(j, i + 1); // 從之前的j繼續往後找
            // j往後移動，直到 2nd sum >= 1st sum
            while(j <= sz - 2 && nums[j] - nums[i] < nums[i]) ++j;
            k = max(k, j);    // 從之前的k繼續往後找
            // k往後移動，直到 3rd sum >= 2nd sum不成立
            while(k <= sz - 2 && nums[sz - 1] - nums[k] >= nums[k] - nums[i]) ++k;
            rtn += k - j;
            rtn %= mod;
        }
        return rtn;
    }
};

1838. Frequency of the Most Frequest Element

  1. 因為數字只能往上加，不能往下遞減。所以只能對齊比自己大的數字。
  2. 先進行排序
  3. 針對每個數字，看看比他還小的數字中，有幾個可以對齊上來。假設有(right - left + 1)個數字對齊到nums[right]，則這數的綜合是
    (right - left + 1) * nums[right]
  4. 使用cur來記錄目前right - left + 1中的數字總和
  5. 如果(right - left + 1) * nums[right] > cur + k，表示把k加到這些數字也湊不到這麼長一樣的nums[right]，所以left向前進。

















class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        int left = 0, ans = 1;
        long cur = 0;
        sort(begin(nums), end(nums)); //O(NlogN)
        for(int right = 0; right < nums.size(); ++right) { // O(N)
            cur += nums[right];
            while((long)(right - left + 1) * nums[right] > cur + k)
                cur -= nums[left++];
            ans = max(ans, right - left + 1);
        }
        return ans;
        // time  : O(NlogN + N) = O(NlogN)
        // space : O(1)
    }
};
tags: leetcode 刷題
Select a repo