[Algorithm][前缀和][和为K的子数组][和可被K整除的子数组][连续数组][矩阵区域和]详细讲解

这篇具有很好参考价值的文章主要介绍了[Algorithm][前缀和][和为K的子数组][和可被K整除的子数组][连续数组][矩阵区域和]详细讲解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


1.和为 K 的子数组

1.题目链接

  • 和为 K 的子数组

2.算法原理详解

  • 分析:因为有负数的存在
    • 无法使用"双指针"优化,因为区间求和不具备单调性
    • 可能已经找到前缀和为k的子数组了,但是后面仍然可能会有更长的和为k的子数组存在
  • 思路:前缀和 + 哈希表
    • 前缀和i位置为结尾的所有的子数组
      • 将问题转化为:在[0, i - 1]区间内,有多少个前缀和等于sum[i] - k
      • 此时,该连续区间问题就可以转化为一个前缀和问题了
    • 哈希表<int, int> -> <前缀和, 次数>
  • 细节处理
    • 前缀和加入哈希表的时机?
      • 由于是在[0, i - 1]区间内,找有多少个前缀和等于sum[i] - k
      • 所以在计算i位置之前,哈希表里面只保存[0, i - 1]位置的前缀和
    • 不用真的创建一个前缀和数组
      • 因为只关⼼在i位置之前,有多少个前缀和等于sum[i] - k
      • 用一个变量sum来标记前一个位置的前缀和即可
    • 如果整个前缀和等于k呢?
      • hash[0] = 1
      • 即:默认哈希表中存在一个前缀和为0的值
        [Algorithm][前缀和][和为K的子数组][和可被K整除的子数组][连续数组][矩阵区域和]详细讲解,OJ,算法,前缀和,和为K的子数组,和可被K整除的子数组,连续数组,矩阵区域和,leetcode

3.代码实现

int SubarraySum(vector<int>& nums, int k) 
{
    unordered_map<int, int> hash; // <前缀和, 次数>
    hash[0] = 1;

    int ret = 0, sum = 0; // 标识前一个位置的前缀和
    for(auto& e : nums)
    {
        sum += e; // 计算当前位置的前缀和

        if(hash.count(sum - k))
        {
            ret += hash[sum - k];
        }

        hash[sum]++; // 将i位置的前缀和入hash
    }

    return ret;
}

2.和可被 K 整除的子数组

1.题目链接

  • 和可被 K 整除的子数组

2.算法原理详解

  • 前置知识
    • 同余定理(a - b) / p = k -> a % p == b % p
    • C++ [ 负数 % 正数 ] [负数 \% 正数] [负数%正数]结果修正
      • 结果 [ 负数 % 正数 ] [负数 \% 正数] [负数%正数] -> 负数
        • 尽可能让商,进行向0取整
      • 修正a % p + p
      • 正负统一(a % p + p) % p
  • 分析:因为有负数的存在
    • 无法使用"双指针"优化,因为区间求和不具备单调性
    • 可能已经找到前缀和可以被k整除的子数组了,但是后面仍然可能会有更长的前缀和可以被k整除的子数组存在
  • 思路:前缀和 + 哈希表
    • 前缀和i位置为结尾的所有的子数组
      • 将问题转化为:在[0, i - 1]区间内,有多少个前缀和的余数等于(sum % k + k) % k
      • 此时,该连续区间问题就可以转化为一个前缀和问题了
    • 哈希表<int, int> -> <前缀和, 次数>
  • 细节处理
    • 前缀和加入哈希表的时机?
      • 由于是在[0, i - 1]区间内,找有多少个前缀和的余数等于(sum % k + k) % k
      • 所以在计算i位置之前,哈希表里面只保存[0, i - 1]位置的前缀和的余数
    • 不用真的创建一个前缀和数组
      • 因为只关⼼在i位置之前,有多少个前缀和的余数等于(sum % k + k) % k
      • 用一个变量sum来标记前一个位置的前缀和即可
    • 如果整个前缀和等于k呢?
      • hash[0] = 1
      • 即:默认哈希表中存在一个前缀和余数为0的值
        [Algorithm][前缀和][和为K的子数组][和可被K整除的子数组][连续数组][矩阵区域和]详细讲解,OJ,算法,前缀和,和为K的子数组,和可被K整除的子数组,连续数组,矩阵区域和,leetcode

3.代码实现

int subarraysDivByK(vector<int>& nums, int k) 
{
    unordered_map<int, int> hash;// <前缀和余数, 次数>
    hash[0] = 1;

    int sum = 0, ret = 0; // 用于标记前一个位置的前缀和
    for(auto& e : nums)
    {
        sum += e; // 计算当前位置的前缀和

        int tmp = (sum % k + k) % k; // 修正后的余数
        if(hash.count(tmp))
        {
            ret += hash[tmp];
        }

        hash[tmp]++; // 将i位置的前缀和的余数入hash
    }

    return ret;
}

3.连续数组

1.题目链接

  • 连续数组

2.算法原理详解

  • 问题转化

    • 将所有的 0 0 0修改成 − 1 -1 1
    • 在数组中,找出最长的子数组,使子数组中所有元素的和为0
  • [和为k的子数组] -> [和为0的子数组]

  • 思路:前缀和 + 哈希表

    • 前缀和i位置为结尾的所有的子数组
      • 将问题转化为:在[0, i - 1]区间内,有多少个前缀和等于sum
      • 此时,该连续区间问题就可以转化为一个前缀和问题了
    • 哈希表<int, int> -> <前缀和,下标>
      [Algorithm][前缀和][和为K的子数组][和可被K整除的子数组][连续数组][矩阵区域和]详细讲解,OJ,算法,前缀和,和为K的子数组,和可被K整除的子数组,连续数组,矩阵区域和,leetcode
  • 细节处理

    • 前缀和加入哈希表的时机?`
      • 在计算i位置之前,哈希表里面只保存[0, i - 1]位置的前缀和
      • 所以,使用完之后,丢进哈希表
    • 如果哈希表中有重复的(sum, i),如何存?
      • 因为要找最长的子数组
      • 所以只需要保留前面的那一对(sum, i)即可
    • 不用真的创建一个前缀和数组
      • 因为只关⼼在i位置之前,有多少个前缀和等于sum
      • 用一个变量sum来标记前一个位置的前缀和即可
    • 默认的前缀和为0的情况,如何存?
      • hash[0] = -1
    • 长度怎么算?
      • i - j
        [Algorithm][前缀和][和为K的子数组][和可被K整除的子数组][连续数组][矩阵区域和]详细讲解,OJ,算法,前缀和,和为K的子数组,和可被K整除的子数组,连续数组,矩阵区域和,leetcode

3.代码实现

int FindMaxLength(vector<int>& nums) 
{
    unordered_map<int, int> hash; // <前缀和, 下标>
    hash[0] = -1; // 默认有一个前缀和为0的情况

    int sum = 0, len = 0; // 标记前一次的前缀和
    for(int i = 0; i < nums.size(); i++)
    {
        sum += nums[i] == 0 ? -1 : 1;

        if(hash.count(sum))
        {
            len = max(len, i - hash[sum]); // 更新最大长度
        }
        else
        {
            hash[sum] = i; // 将(sum, i)入hash
        }
    }

    return len;
}

4.矩阵区域和

1.题目链接

  • 矩阵区域和

2.算法原理详解

  • 该题就是对**[二维前缀和]**的一个实际应用

  • 左上角/右上角坐标可能会越界

    • 左上角:
      • x 1 = m a x ( 0 , i − k ) + 1 x_1 = max(0, i - k) + 1 x1=max(0,ik)+1
      • y 1 = m a x ( 0 , j − k ) + 1 y_1 = max(0, j - k) + 1 y1=max(0,jk)+1
    • 右下角
      • x 2 = m i n ( m − 1 , i + k ) + 1 x_2 = min(m - 1, i + k) + 1 x2=min(m1,i+k)+1
      • y 2 = m i n ( n − 1 , j + k ) + 1 y_2 = min(n - 1, j + k) + 1 y2=min(n1,j+k)+1
        [Algorithm][前缀和][和为K的子数组][和可被K整除的子数组][连续数组][矩阵区域和]详细讲解,OJ,算法,前缀和,和为K的子数组,和可被K整除的子数组,连续数组,矩阵区域和,leetcode
  • 下标的映射关系
    [Algorithm][前缀和][和为K的子数组][和可被K整除的子数组][连续数组][矩阵区域和]详细讲解,OJ,算法,前缀和,和为K的子数组,和可被K整除的子数组,连续数组,矩阵区域和,leetcode文章来源地址https://www.toymoban.com/news/detail-860920.html


3.代码实现

vector<vector<int>> MatrixBlockSum(vector<vector<int>>& mat, int k) 
{
    int row = mat.size(), col = mat[0].size();

    // 预处理前缀和数组
    vector<vector<int>> dp(row + 1, vector<int>(col + 1));
    for(int i = 1; i <= row; i++)
    {
        for(int j = 1; j <= col; j++)
        {
            // 下标映射关系 dp[x, y] -> mat[x - 1][y - 1]
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] \
					- dp[i - 1][j - 1] + mat[i - 1][j - 1];
        }
    }

    // 使用前缀和数组
    vector<vector<int>> ret(row, vector<int>(col));
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            // 下标映射关系 ret[x][y] -> dp[x + 1][y + 1]
            int x1 = max(0, i - k) + 1;
            int y1 = max(0, j - k) + 1;
            int x2 = min(row - 1, i + k) + 1;
            int y2 = min(col - 1, j + k) + 1;

            ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] \
					- dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
        }
    }

    return ret;
}

到了这里,关于[Algorithm][前缀和][和为K的子数组][和可被K整除的子数组][连续数组][矩阵区域和]详细讲解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 560. 和为 K 的子数组【哈希、前缀和】

    560. 和为 K 的子数组 给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的连续子数组的个数 。 示例 1: 输入:nums = [1,1,1], k = 2 输出:2 示例 2: 输入:nums = [1,2,3], k = 3 输出:2 提示: 1 = nums.length = 2 * 104 -1000 = nums[i] = 1000 -107 = k = 107 C代码:哈希、前缀和

    2024年02月02日
    浏览(44)
  • hot100:10和为k的子数组

    题目链接: LeetCode 热题 100 - 学习计划 - 力扣(LeetCode)全球极客挚爱的技术成长平台 算法思想: 法一(暴力法): 使用两层for循环列举出所有的子数组,使用一个变量sum求得子数组的和并判断是否为k 法二(前缀和+哈希表): 前缀和:前缀和就是从下标为0的元素开始到当

    2024年01月23日
    浏览(44)
  • 【LeetCode热题100】【子串】和为 K 的子数组

    题目 给你一个整数数组  nums  和一个整数  k  ,请你统计并返回  该数组中和为  k   的子数组的个数  。 子数组是数组中元素的连续非空序列。 示例 1: 示例 2: 提示: 1 = nums.length = 2 * 104 -1000 = nums[i] = 1000 -107 = k = 107 暴力  直接两层循环找出所有连续子数组的和,这个

    2024年01月19日
    浏览(44)
  • 剑指 Offer II 010. 和为 k 的子数组

    给定一个整数数组和一个整数 k ,请找到该数组中和为 k 的连续子数组的个数。 示例 1: 示例 2: 提示: 这个题目做出来不难,直接暴力枚举。但是利用哈希表和前缀和优化的过程我一直不是很理解,所以写下这篇文章来一点一点的研究,希望能对大家有所帮助 首先,先看最

    2023年04月16日
    浏览(42)
  • leetcode分类刷题:易混题辨析一、209. 长度最小的子数组 vs 560. 和为K的子数组

    1、刷题慢慢积累起来以后,遇到相似的题目时,会出现算法思路混淆了 2、这两道题都是对 连续子数组加和 进行考察,细节区别在于数组元素在209. 长度最小的子数组为 正整数(窗口增加元素递增,减少元素递减) ,在560. 和为K的子数组为 整数 3、209. 长度最小的子数组采

    2024年02月10日
    浏览(39)
  • Leetcode-每日一题【剑指 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 前置知识 前缀和

    2024年02月15日
    浏览(47)
  • 【1015. 可被 K 整除的最小整数】

    来源:力扣(LeetCode) 描述: 给定正整数 k ,你需要找出可以被 k 整除的、仅包含数字 1 的最 小 正整数 n 的长度。 返回 n 的长度。如果不存在这样的 n ,就返回 -1 。 注意: n 不符合 64 位带符号整数。 示例 1: 示例 2: 示例 3: 提示: 1 = k = 10 5 方法:遍历 思路与算法 题

    2024年02月03日
    浏览(70)
  • 【1262. 可被三整除的最大和】

    来源:力扣(LeetCode) 描述: 给你一个整数数组 nums ,请你找出并返回能被三整除的元素最大和。 示例 1: 示例 2: 示例 3: 提示: 1 = nums.length = 4 * 10 4 1 = nums[i] = 10 4 方法:贪心 + 正向思维 我们把数组中的数分成三部分 a, b, c,它们分别包含所有被 3 除余 0 , 1, 2 的数。显

    2024年02月10日
    浏览(37)
  • LeetCode 1262. 可被三整除的最大和

    力扣题目链接:https://leetcode.cn/problems/greatest-sum-divisible-by-three/ 给你一个整数数组  nums ,请你找出并返回能被三整除的元素最大和。   示例 1: 示例 2: 示例 3:   提示: 1 = nums.length = 4 * 10^4 1 = nums[i] = 10^4 一个数对3取模,只有0、1、2这三种情况。 我们只需要对nums中所有数

    2024年02月09日
    浏览(34)
  • Leetcode【1010】总持续时间可被 60 整除的歌曲

    最近忙于毕设,leetcode也就随缘刷刷每日一题了。 在歌曲列表中,第 i 首歌曲的持续时间为 time[i] 秒。 返回其总持续时间(以秒为单位)可被 60 整除的歌曲对的数量。形式上,我们希望下标数字 i 和 j 满足 i j 且有 (time[i] + time[j]) % 60 == 0 。 示例1: 来源:力扣(LeetCode) 链

    2024年02月03日
    浏览(79)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包