zl程序教程

您现在的位置是:首页 >  后端

当前栏目

【数组 | 哈希表】 剑指 Offer II 010. 和为 k 的子数组 | 剑指 Offer II 011. 0 和 1 个数相同的子数组

数组哈希 II Offer 个数 相同 010 011
2023-09-27 14:29:25 时间

剑指 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

分析

哈希表 + 前缀和

  1. 我们定义 pre[i] 为 [0…i] 里所有数的和,则 pre[i] 可以由 pre[i−1] 递推而来
pre[i] = pre[i - 1] + nums[i];
  1. 那么「[j…i]这个子数组和为 k 」这个条件可以转化为
pre[i] - pre[j - 1] == k;

pre[j - 1] == pre[i] - k;
  1. 定义一个哈希表,键用来存放当前遍历的前缀和,值都计数为1。
  2. 每次遍历数组的元素,都将其前缀和插入到哈希表,如果发现【前缀和 - k】在哈希表中存在,则对返回值加上该键所对应的值。

代码

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> hash_map;
        int cursum = 0, ans = 0;

        hash_map[0]++;
        for (int i = 0; i < nums.size(); ++i)
        {
            cursum += nums[i];
            if (hash_map.count(cursum - k))
            {
                ans += hash_map[cursum - k];
            }
            hash_map[cursum]++;
        }
        return ans;
    }
};

时间复杂度:O(n);
空间复杂度:O(n);

剑指 Offer II 011. 0 和 1 个数相同的子数组

题目

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组,并返回该子数组的长度。

原题链接:【点此查看】

示例1:

输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 01 的最长连续子数组。

示例2:

输入: nums = [0,1,0]
输出: 2
说明: [0, 1] ([1, 0]) 是具有相同数量 01 的最长连续子数组。

注意:


    1 <= nums.length <= 105
    nums[i] 不是 0 就是 1

分析

在预处理前缀和时,将 nums[i] 为 0 的值当做 −1 处理。

从而将问题转化为:如何求得最长一段区间和为 0 的子数组。

同时使用「哈希表」来记录「某个前缀和