暑假刷题（7/8）

题目：给你一个下标从 0 开始的整数数组 nums ，其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k。从数组中选出任意 k 名学生的分数，使这 k 个分数间 最高分 和 最低分 的 差值 达到 最小化 。返回可能的 最小差值 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-difference-between-highest-and-lowest-of-k-scores

思路：可以近似看作二维数组的模型，先对nums从小到大排序，然后像滑动窗口一样，把k个元素看成一个数组，取首元素i和尾元素i-k+1，求其差。循环，比较。得出首位元素的最小差。

 代码

class Solution {
public:
    int minimumDifference(vector& nums, int k) {
        if(k == 1){
            return 0;
        }
        int len = nums.size();
        sort(nums.begin(), nums.end());
        int difference = INT_MAX;
        for(int i = 0;i + k - 1 < len; i++){
            int d = nums[i + k - 1] - nums[i];
            if(d < difference){
                difference = d;
            }
        }
        return difference;
    }
};

题目：给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

思路：滑动窗口的想法。

代码：

class Solution {
public:
    int numSubarrayProductLessThanK(vector& nums, int k) {
        int len = nums.size();
        int sum = 0;
        int mul = 1;
        int i = 0;
        for (int j = 0; j < len; j++) {
            mul *= nums[j];
            while (i <= j && mul >= k) {
                mul /= nums[i];
                i++;
            }
            sum += j - i + 1;
        }
        return sum;
    }
};

做不来啦，后面的，虽然也是滑动窗口。