Slide Window

Posted on Edited on In
Symbols count in article: 1.3k Reading time ≈ 1 mins.

滑动窗口算法

该算法是通过使用特定大小的子列表，在遍历完整列表的同时进行特定的操作，以达到降低了循环的嵌套深度。

基本示例

经典使用

  • 连续元素最大和

    给定数据，获取数据中n个连续元素，最大的和。
    input ：[-3,3,1,-3,2,4,7] n=3
    output : 13

  • Brute Force

  • Slide Window

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    int maxSum(int arr[], int n, int k) 
    { 
        // Initialize result 
        int max_sum = INT_MIN; 
      
        // Consider all blocks starting with i. 
        for (int i = 0; i < n - k + 1; i++) { 
            int current_sum = 0; 
            for (int j = 0; j < k; j++) 
                current_sum = current_sum + arr[i + j]; 
      
            // Update result if required. 
            max_sum = max(current_sum, max_sum); 
        } 
      
        return max_sum; 
    }

  • 最长无重复子字符串

    给定字符串，计算最长子字符串的长度，该子字符串满足如下条件：

    1. 是给定字符串的字符串
    2. 子字符串中无重复字符
      input：”abcabcbb”
      output: 3

原题链接

  • Brute Force

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            int n = s.size();
            int ans = 0;
            for(int i=0; i<n; i++){
                for(int j=i+1; j<=n; j++){
                    if(allUnique(s,i,j)) ans=max(ans,j-i);
                }
            }
            return ans;
        }
        
        bool allUnique(string s,int start, int end){
            unordered_set<char> seen;
            for(int i=start; i<end; i++){
                char ch=s[i];
                if(seen.count(ch))return false;
                seen.insert(ch);
            }
            return true;
        }
    };

  • slide window

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
    public:
         int lengthOfLongestSubstring(string s) {
             int n = s.length(), ans = 0;
             vector<int> index;
             index.assign(128,0);
            // current index of character
            // try to extend the range [i, j]
             for (int j = 0, i = 0; j < n; j++) {
                i = max(index[s[j]], i);
                ans = max(ans, j - i + 1);
                index[s[j]] = j + 1;
             }
            return ans;
        }
    };