[Leetcode笔记] 滑动窗口相关

前言

今天做leetcode的时候遇到一道滑动窗口相关的题目，题目具体内容如下：

思路

这道题很显然需要用到滑动窗口，肯定不是让你傻乎乎一遍一遍去遍历数组的内容然后遍历尝试

流程：

1. 先算数组的总大小。
2. 使用while计算滑动窗口数量，然后计算相应的长度。
3. 遍历，尝试寻找右值
4. 遍历寻找左值

具体代码如下：

int minSizeSubarray(vector<int> &nums, int target) {
        
        long long total = std::accumulate(nums.begin(), nums.end(), 0LL);// 计算数组的总和        
        int n = nums.size();    // 数组长度        
        int ans = INT_MAX;      // 返回值       
        int left = 0;           //左指针
        long long sum = 0;      //总和

        //从0开始遍历右指针  
        for (int right = 0; right < n * 2; right++) {
            sum += nums[right % n];
            while (sum > target % total) {
                sum -= nums[left++ % n];
            }
            if (sum == target % total) {
                ans = min(ans, right - left + 1);
            }
        }
        return ans == INT_MAX ? -1 : ans + target / total * n;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

题目2

Leetcode 2269 找到一个数字的K美丽值

int divisorSubstrings(int num, int k) {
        string s = to_string(num);   // num 十进制表示字符串
        int n = s.size();
        int res = 0;
        for (int i = 0; i <= n - k; ++i) {
            // 枚举所有长度为 k 的子串
            int tmp = stoi(s.substr(i, k));
            if (tmp && num % tmp == 0) {
                ++res;
            }
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13