likes
comments
collection
share

剑指 Offer（专项突击版）第9|10题

作者站长头像
站长
· 阅读数 51

前言

  • 现在前端要求变高了,找工作的时可能会碰上算法题,每天刷几道算法题做足准备,今天是《剑指 Offer（专项突击版）》第9|10题。

剑指 Offer II 009. 乘积小于 K 的子数组

给定一个正整数数组 nums和整数 k ，请找出该数组内乘积小于 k 的连续的子数组的个数。

难度：中等

示例 1:
输入: nums = [10,5,2,6], k = 100 输出: 8 解释: 8 个乘积小于 100 的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。 需要注意的是 [10,5,2] 并不是乘积小于100的子数组。 
示例 2:
输入: nums = [1,2,3], k = 0 输出: 0

提示: 
● 1 <= nums.length <= 3 * 104
● 1 <= nums[i] <= 1000
● 0 <= k <= 106

知识点： 数组 滑动窗口

方法一： 活动窗口

和面试题8一样，用指针P1和P2指向数组中的两个数字，两个指针之间的数字组成一个子数组。指针P1永远不会走到指针P2的右边。两个指针初始化都指向数组的第1个数字（下标为0的数字）。

如果两个指针之间的子数组中数字的乘积大于或等于k，则向右移动指针P1。向右移动指针P1相当于从子数组中删除最左边的数字，由于数组中的数字都是正整数，因此子数组中数字的乘积就会变小。

目标是求出所有数字乘积小于k的子数组的个数，一旦向右移动指针P1到某个位置时子数组的乘积小于k，就不需要再向右移动指针P1。这是因为只要保持指针P2不动，向右移动指针P1形成的所有子数组的数字乘积就一定小于k。此时两个指针之间有多少个数字，就有几个子数组。将数字累加就是最终结果。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var numSubarrayProductLessThanK = function(nums, k) {
    let len = nums.length;
    let res = 0;
    let product = 1;
    let P1 = 0;
    for (let P2 = 0; P2 < len; P2++) {
        product *= nums[P2];
        while (P1 <= P2 && product >=k ) {
            product /= nums[P1];
            P1++;
        }
        res += P2 - P1 + 1;
    }
    return res;
};

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 nums 的长度。两个端点 P1 和 P2 的增加次数都不超过 n。
  • 空间复杂度：O(1)。

剑指 Offer II 010. 和为 k 的子数组

给定一个整数数组和一个整数 k ****， 请找到该数组中和为 k ****的连续子数组的个数。

难度：中等

示例 1：
输入:nums = [1,1,1], k = 2 输出: 2 解释: 此题 [1,1] 与 [1,1] 为两种不同的情况 
示例 2：
输入:nums = [1,2,3], k = 3 输出: 2 

提示:
● 1 <= nums.length <= 2 * 104
● -1000 <= nums[i] <= 1000
● -107 <= k <= 107

知识点： 数组 哈希表 前缀和

方法一：枚举

使用双指针解决子数组之和的面试题有一个前提条件——数组中的所有数字都是正数。如果数组中的数字有正数、负数和零，那么双指针的思路并不适用，这是因为当数组中有负数时在子数组中添加数字不一定能增加子数组之和，从子数组中删除数字也不一定能减少子数组之和。

该题最简单想到的就是利用枚举，使用双层遍历，先固定左边界，然后枚举右边界。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    const  len = nums.length;
    let count = 0;
    for (let l = 0; l < len; l++) {
        let sum = 0;
        for (let r = l; r < len; r++) {
            sum += nums[r];
            if(sum === k) {
                count ++;
            }
        }
    }
    return count;
};

复杂度分析：

  • 时间复杂度：O(N^2)，这里 N 是数组的长度；
  • 空间复杂度：O(1)。

方法二：前缀和 + 哈希表

基于方法一利用数据结构进行进一步的优化。

定义 pre[i 为 [0..i] 里所有数的和，则 pre[i] 可以由 pre[i−1] 递推而来，即：pre[i]=pre[i−1]+nums[i]

那「[j..i] 这个子数组和为 k 」这个条件可以转化为：pre[i]−pre[j−1]==k

简单移项可得符合条件的下标 j 需要满足：pre[j−1]==pre[i]−k

考虑以 i 结尾的和为 k 的连续子数组个数时只要统计有多少个前缀和为 pre[i]−k 的 pre[j] 即可。

建立哈希表 mp，以和为键，出现次数为对应的值，记录 pre[i]出现的次数，从左往右边更新 mp 边计算答案，那么以 i 结尾的答案 mp[pre[i]−k] 即可在 O(1) 时间内得到。最后的答案即为所有下标结尾的和为 k 的子数组个数之和。

需要注意的是，从左往右边更新边计算的时候已经保证了mp[pre[i]−k] 里记录的 pre[j] 的下标范围是 0≤j≤i 。同时，由于pre[i] 的计算只与前一项的答案有关，可以不用建立 pre 数组，直接用 pre 变量来记录 pre[i−1] 的答案即可。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    const mp = new Map();
    mp.set(0,1);
    let count = 0, pre = 0;
    for (const x of nums) {
        pre += x;
        if(mp.has(pre - k)) {
            count += mp.get(pre - k);
        }

        if(mp.has(pre)) {
            mp.set(pre, mp.get(pre) + 1);
        } else {
            mp.set(pre, 1);
        }
    }
    return count;
};

复杂度分析

  • 时间复杂度：O(n)，其中 n 为数组的长度。遍历数组的时间复杂度为 O(n)，中间利用哈希表查询删除的复杂度均为 O(1)，因此总时间复杂度为 O(n)。
  • 空间复杂度：O(n)，其中 n 为数组的长度。哈希表在最坏情况下可能有 n 个不同的键值，因此需要 O(n) 的空间复杂度。

so

剑指 Offer（专项突击版）第9|10题

传送门

转载自:https://juejin.cn/post/7173216983373545508
评论
请登录