大小为K的子集的乘积和 - 腾讯云开发者社区 - 腾讯云

开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

【HDU 5363】Key Set（和为偶数的子集个数）

Sample Input 4 1 2 3 4 Sample Output 0 1 3 7 题意：求1 2 3 ... n 的所有子集中和为偶数的子集个数，mod 1000000007...分析：数学归纳法证明和为偶数的子集有2n-1-1个：当n=1时，有a1=0个假设n=k时，有ak=2k-1-1个子集和为偶数，若k+1为偶数，则ak个子集加上这个偶数，和还是偶数，这个偶数单独一个集合...，和就是这个偶数，ak+1=ak*2+1=2k-1 　若k+1为奇数，前k个数共有2k个子集，其中一个空集和为0，和为奇数的子集有2k-1-ak=2k-1个，和为奇数的子集加上k+1这个数，和变成了偶数...，因此ak+1=ak+2k-1=2k-1 综合1,2得系列1 2 ... n 和为偶数的子集有2n-1-1个接下来用快速幂即可。...2,ans=1; n--; while(n){ if(n&1)ans=(ans*k)%M; k=(k*k)%M;

4742 0

最后 K 个数的乘积

getProduct(int k) – 返回当前数字列表中，最后 k 个数字的乘积。 – 你可以假设当前列表中始终至少包含 k 个数字。...题目数据保证：任何时候，任一连续数字序列的乘积都在 32-bit 整数范围内，不会溢出。...最后 2 个数字的乘积是 5 * 4 = 20 productOfNumbers.getProduct(3); // 返回 40 。...最后 2 个数字的乘积是 4 * 8 = 32 提示： add 和 getProduct 两种操作加起来总共不会超过 40000 次。...优化：在获取乘积的时候才开始批量处理add进来的数，不要add一个就处理一次，太浪费时间 class ProductOfNumbers { vector product; vector<

3933 0

您找到你想要的搜索结果了吗？

是的

没有找到

乘积小于k的连续子数组个数

和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。...示例 1：输入：nums = [10,5,2,6], k = 100 输出：8 解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、...需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。...定义两个指针，left与right，都是从起始位置开始进行： •如果right右移，left到right到总乘积仍然小于k，则right继续右移直到不满足上述条件•此时，以left开始，right截止时候到满足次数为...right-left+1•此时left+1，并将总的乘积除以left位置的元素以保证此时left～right之间的元素乘积满足小于k的要求•每次满足要求后，left～right之间的次数都满足right-left

4541 0

和至少为K的最短数组

问题描述返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。如果没有和至少为 K 的非空子数组，返回 -1 。...然后发现数组中存在负值，前缀和不一定是递增的，因此上述做法不行。先说做法，再解释其正确性。首先计算前缀和数组记做sum，一般的会让前缀和数组多一个0元素。...此外遍历过程中会使前缀和元素维持一个单调队列（从队头到队尾单调递增）的结构遍历前缀和数组，分别找到以当前元素cur为右边界时满足子数组和大于等于K的左边界i，即找到满足如下条件里cur最近的i， sum...因此若存在i2，此时i1必不为最短子数组的左边界。问题二：为何直接可以弹出满足条件的队头元素，会不会以队头元素为左边界时满足条件的最短的子数组在cur后面？...-1 : ans; } } 时间复杂度为O（N）, 额外空间复杂度亦为O（N）。

5012 0

滑动窗口之乘积小于k的子数组

乘积小于k的子数组给定一个正整数数组 nums和整数 k 。请找出该数组内乘积小于 k 的连续的子数组的个数。...这种解法同样是刚开始左右指针指在同一个地方，然后由于乘积小于k，r可以向右移动，乘积继续变化，直到乘积大于等于k，我们就需要进行一些操作了。...让我们来想一想，我们需要满足的条件是连续数组内的数乘积小于k，当右指针一直向右移动使得乘积不断增大时，总会有大于等于k的时候，那个时候，我们就需要改变l了，在这种情况下，我们计算的ans就不是现在的r-l...因为当l不变、r向右移动时，我们的乘积一直都是非递减的，如果当前右指针移动到的位置使得l到r不满足乘积小于k，那我们再继续移动右指针，乘积一定依旧不满足小于k，那就说明这个l我们已经“利用”完了，l可以退出滑动窗口了...~ 所以l的改变就取决于乘积除以要移除的nums[l]的结果，直到这个结果小于k时，l就不需要再变化了这个时候我们就能求取当前的l到r对应的ans值了（因为已经满足乘积小于k这个条件了） /** *

7361 0

和为 K 的子数组

，这样加快了暴力破解计算和的过程； 3.前缀树+hash 假设区间[left, right]的和为k,即前right项的和-前left项的和=k,换句话说就是：前left项之和=前right项之和-k...因此我们可以遍历一遍数组，记录下前i项的和sum,用Map的健存储sum，Map的值存储sum出现的次数。...假设当前扫到第i位，记录它的前i项和sum，用该和减去k，即sum-k，判断sum-k是否为某个位置的前n项和，若是，更新统计量。...{ //存储从0~i项的和 int[] sumArr=new int[nums.length+1]; //存储值 for (int i...K的话，即sum-k=0的时候我们需要赋初值，就是1。

3112 0

和为K的子数组

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。...示例 1 : 输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。...前缀和: 当前元素之前的所有元素的和哈希表里面放前缀和,前缀和出现的次数遍历数组每一个元素,判断当前“前缀和”与历史前缀和...，差分出一个子数组，该历史前缀和出现过 c 次，等价于当前项找到 c 个子数组求和等于 k。...if(map.containsKey(pre-k)){ // pre-pre历史前缀和=k pre-k=历史前缀和 count+=map.get(pre-k);

5643 0

LeetCode题解——和为 k 的子数组

更新一篇发布在力扣上的题解，900+的watch记录一波，题目链接： https://leetcode-cn.com/problems/QTMn0o/ 解题思路 1、本题需要求出子数组之和为k的数组个数...我们可以先统计一下前n项的和值出现的次数，也就是所谓的前缀和，这里将前缀和为0也统计进来： 1）此时假设k=6，我们肉眼可见的数组和值为6的是【1，2，3】，那么对应到前缀和里面就是 3 这个位置，...它其实可以看成 3 - 0 得到的区间和值； 2）再假设k=7，那么我们可以发现数组和值为7的是【3，4】，此时我们可以发现在前缀和中没有找到和值为7的，那么说明该子数组的起始位置并非0；此时按照滑动窗口的思路就应该移动左指针...，当左指针移动到索引2时就可以发现，索引2、3构成的子数组是满足条件的，借助上一个假设我们可以发现这里的和值7其实可以通过 4 － 2 来得到，因此我们实际上可以通过前缀和的差值来得出各个区间的和值，也就可以轻易得到和值为...hash表中寻找的键值是sum-k，因为直接寻找k只可以找到那些起始位置为0的子数组，而寻找sum-k因为我们事先插入了一个0的键值，因此这里也不会忽略掉这种情况。

1.1K2 0

和为K的子数组（LeetCode 560）

考虑以 i 结尾和为 k 的连续子数组个数，我们需要统计符合条件的下标 j 的个数，其中 0≤j≤i 且 [j…i] 这个子数组的和恰好为 k 。...我们知道方法一的瓶颈在于对每个 i，我们需要枚举所有的 j 来判断是否符合条件。除了通过加法累加 i 到 j 来判断 [j…i] 这个子数组和是否为 k，我们还可以通过前缀和的减法来判断。...我们定义 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 - 1]）的个数即可。

2011 0

划分为k个相等的子集

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。...示例 1：输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4 输出： True 说明：有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。...注意: 1 k <= len(nums) <= 16 0 < nums[i] < 10000 算是比较慢的解法吧，先判断数组总和是否是k的倍数，不是就false，然后置一vis数组标记是否访问过...，dfs从0到k-1 共k个集合，做完一个做下一个（做完的意思是填正好sum/k的值） class Solution { public boolean canPartitionKSubsets(...avg, int k, int temp, int index ){ if (k == 0 ) return true; if (temp == 0)

1.1K3 0

LeetCode-560-和为K的子数组

# LeetCode-560-和为K的子数组给定一个整数数组和一个整数 **k，**你需要找到该数组中和为 k 的连续的子数组的个数。...# 解题思路方法1、暴力累加：以数组中每一个数字作为起点，不断向后累加，找到一个累加和为k的就让count++ 当以下一个数字为起点时，重置sum为0，即可得到最终结果方法2、哈希表：更好的题解...]−k 所以我们考虑以i结尾的和为k的连续子数组个数时只要统计有多少个前缀和为 sum[i]−k的 sum[j]即可。...我们建立哈希表 mp，以和为键，出现次数为对应的值，记录 sum[i]出现的次数，从左往右边更新 mp边计算答案，那么以 i结尾的答案 mp[sum[i]−k] 即可在 O(1)时间内得到。...最后的答案即为所有下标结尾的和为 k的子数组个数之和。需要注意的是，从左往右边更新边计算的时候已经保证了mp[sum[i]−k]里记录的 sum[j]的下标范围是 0≤j≤i 。

2431 0

和为K的子数组

在前缀和的基础上，结合了hash来优化，也就是两数之和那道题。两个地方需要注意。一、需要的前缀和可能出现多次，那么每次都得算上。二、前缀和为0也是一种情况，并且是必要的，需要手动添加。...例如目标为0。题目给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。...示例 1 : 输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。说明 : 数组的长度为 [1, 20,000]。...数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。...// 子串长度为0（在母串最前面），前缀和为0，出现次数+1（原本为0） qzh.put(0, 1); // 前缀和 int sum

2472 0

力扣560——和为K的子数组

这道题主要是找规律，优化的时候可以利用哈希表和数组的特性。原题给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。...示例 1 : 输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。说明 : 数组的长度为 [1, 20,000]。...原题url：https://leetcode-cn.com/problems/subarray-sum-equals-k/ 解题一开始的想法肯定就是利用暴力解法了，三层 for 循环的那种，第1层和第...int count = 0; // 求和 int sum = 0; // key为中间求出了哪些和，value为当前和有几种情况...真正能够保证达到O(1)的数据结构，是数组（用空间换取时间）。那这个用来存储的一维数组究竟长度该设置为多少呢？自然就是找出数组中子数组之和的最大值和最小值，两者求差，结果就是最终的数组长度。

4413 0

和为 K 的子数组

和为 K 的子数组题目描述：给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。...* 10^4 -1000 <= nums[i] <= 1000 -1e7 k <= 1e7 方法1：暴力解法：思路和算法考虑以 i 结尾和为 k 的连续子数组个数，我们需要统计符合条件的下标...jj 的个数，其中0≤j≤i 且 [j…i] 这个子数组的和恰好为 k 。...pre[i]−pre[j−1]==k 简单移项可得符合条件的下标 jj 需要满足 pre[j−1]==pre[i]−k 所以我们考虑以 i结尾的和为 k 的连续子数组个数时只要统计有多少个前缀和为pre...最后的答案即为所有下标结尾的和为 k 的子数组个数之和。需要注意的是，从左往右边更新边计算的时候已经保证了mp[pre[i]−k] 里记录的 pre[j] 的下标范围是 0≤ j≤ i 。

7403 0

前缀和 LeetCode 560.和为K的子数组

前缀和 LeetCode 560.和为K的子数组给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。...示例 1：输入：nums = [1,1,1], k = 2 输出：2 示例 2：输入&...#xFF1A;nums = [1,2,3], k = 3 输出：2 提示： 1 <= nums.length <= 2 * 104 -1000 <...;= nums[i] <= 1000 -107 <= k <= 107 前缀和 public int subarraySum(int[] nums, int k) {...) { for (int j = i; j < len; j++) { if (preSum[j + 1] - preSum[i] == k)

3401 0

乘积小于K的子数组（滑动窗口）

找出该数组内乘积小于 k 的连续的子数组的个数。...示例 1: 输入: nums = [10,5,2,6], k = 100 输出: 8 解释: 8个乘积小于100的子数组分别为: [10], [5], [2], [6], [10,5], [5,2],...需要注意的是 [10,5,2] 并不是乘积小于100的子数组。...解题滑动窗口，连续乘积 k，右端点向右扩乘积 >= k，左端点向右收缩 class Solution { //C++ public: int numSubarrayProductLessThanK...// (product*nums[j] >= k) { //乘积大了，左端点移走 product /= nums[i++];//有>=k的数的时候，product可能会变成

5312 0

所有子集的和递归

给一整数 n, 我们需要求前n个自然数形成的集合的所有可能子集中所有元素的和样例给出 n = 2, 返回 6 可能的子集为 {{1}, {2}, {1, 2}}....子集的元素和为 1 + 2 + 1 + 2 = 6 给出 n = 3, 返回 24 可能的子集为 {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}...子集的和为: 1 + 2 + 3 + (1 + 2) + (1 + 3) + (2 + 3) + (1 + 2 + 3) = 24 递归这是个数学题，找到规律就容易做了。...看红色的，是每一个相对于上一个增加的子集，红色的把绿色的去掉就是上一个全部的子集，n的子集应该有一个n-1子集的两倍，还多了什么呢？...就是多了很多个n，有多少个呢，就是n-1的子集数，这个值应该是2^n-1。看规律容易看来，另外也是可以推导的： n个自然数取组合数应该是： ? 这个是高中学的，很简单，二项式定理。

6732 0

划分为k个相等的子集（回溯）

题目给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。...示例 1：输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4 输出： True 说明：有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。...分割等和子集（动态规划）普通回溯，超时，59 / 149 个通过测试用例 class Solution { int target; bool ans = false; int...partsum, i+1); partsum[j] -= nums[i]; } } } }; 优化，从大到小排序，可以尽快的让每个部分的和凑够...从大到小排序 if(nums[0] > target)//最大的数超过了，不行 return false; vector partsum

5051 0

和为 K 的子数组

一、题目给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。...比如要计算a[7]~a[9]子序列的和。我们可以通过sum(a[9]) -sum(a[6])来计算。这样做的好处就是，防止重复的遍历和计算。...那么，理解了前缀和之后，我们就可以尝试对这道题进行解答了，解答步骤如下所示：【步骤1】遍历数组nums，并计算下标i对应的前缀和preSum[i]；【步骤2】然后用preSum[i]减去k值，就是我们还缺少的子序列总和...如果不存在，则说明不匹配；如果存在，则获取到相应的value值。其中，value值表示子序列总和为key的子序列出现的次数。...以上就是本题的解题思路了，为了便于理解，我们以输入参数nums=[1,2,3]，k=3为例。

2522 0

【每日leetcode】47.和为K的子数组

和为K的子数组难度：简单 ❝ 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。...示例 1 : 输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。说明 : 数组的长度为 [1, 20,000]。...数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。 ❞ Solution ❝前缀和+哈希表 ❞ 前缀和：nums 的第 0 项到当前项的和。...每个元素对应一个“前缀和” 遍历数组，根据当前“前缀和”，在 map 中寻找「与之相减 == k」的历史前缀和当前“前缀和”与历史前缀和，差分出一个子数组，该历史前缀和出现过 c 次，等价于当前项找到...c 个子数组求和等于 k。

4095 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭