- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
题目地址: https://leetcode.com/problems/minimum-size-subarray-sum/description/
Given an array of n
positive integers and a positive integer s, find the minimal length of a contiguous
subarray of which the sum ≥ s
. If there isn't one, return 0 instead.
Example:
Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.
Follow up:
找出一个数组中最短连续的子数组,这个子数组的和要>=s.
碰巧今天在《挑战程序设计竞赛》一书中看到这个题,解法称之为虫取法,其实就是双指针。其实看到让连续子数组满足一定条件的很多都用了双指针,比如713. Subarray Product Less Than Kopen in new window。
因为这个题需要求最小值,所以结果初始化为inf,每次移动一下右指针,当和满足条件的时候,更新结果,并移动左指针,同时记得把和删去左边的数字。这里求和的区间是左右都是闭区间。
时间复杂度是O(N),空间复杂度是O(1)。
class Solution:
def minSubArrayLen(self, s, nums):
"""
:type s: int
:type nums: List[int]
:rtype: int
"""
N = len(nums)
l, r = 0, 0
csum = 0
res = float('inf')
while r < N:
csum += nums[r]
while csum >= s:
res = min(res, r - l + 1)
csum -= nums[l]
l += 1
r += 1
return res if res != float('inf') else 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
二刷的时候使用了C++,我同样选择了虫取法,但是对虫取法没有100%的信心,因为很多题目虫取法可能漏掉了解,而不容易发现。还好这个题目只有正整数,比较容易找到移动左右指针的规律,所以虫取法没什么问题。
我定义了两个指针left和right,定义了sum = [left...right)的和,其中区间是左闭右开,这样,right终止条件是right <=N,而满足题目要求的区间的长度是right - left。把这些弄明白之后就很容易写出代码了。
C++代码如下:
class Solution {
public:
// O(N) using two pointer
int minSubArrayLen(int s, vector<int>& nums) {
const int N = nums.size();
if (N == 0) return 0;
int left = 0, right = 0;
// sum = sum[left, right)
long long sum = 0;
int res = INT_MAX;
while (right <= N) {
if (sum >= s) {
res = min(res, right - left);
sum -= nums[left++];
} else {
sum += nums[right++];
}
}
return res == INT_MAX ? 0 : res;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
这个题有个follow up,让我们用o(NlogN)的时间复杂度去求解,很明显地,在考察我们二分。
思路很显然,对于每个位置求数组累积和,然后对于累积和的每个位置,去查找sums[i] - pos的位置在sums中的哪里。这样的话,就得到了一个区间,这个区间的累积和是不小于s的,即为题目所求。
这个题我写的二分是查找第一个不小于某个数字的位置,即lower_bound,这样会造成,当要查找的target不在sums中时,返回的结果是它右边的第一个数字。所以需要做个判断,如果查到了,那么区间长度是i - pos,否则区间长度应该+1.
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
const int N = nums.size();
vector<int> sums;
sums.push_back(0);
for (int i = 0; i < N; ++i) {
sums.push_back(nums[i] + sums.back());
}
int res = INT_MAX;
for (int i = 1; i <= N; ++i) {
int target = sums[i] - s;
if (target < 0) continue;
auto pos = binary_search(sums, target);
if (pos > N) continue;
if (sums[i] - sums[pos] == s)
res = min(res, i - pos);
else if (sums[i] - sums[pos] < s)
res = min(res, i - pos + 1);
}
return res == INT_MAX ? 0 : res;
}
int binary_search(vector<int>& sums, int target) {
const int N = sums.size();
// [l, r)
int l = 0, r = N;
while (l < r) {
int mid = l + (r - l) / 2;
if (sums[mid] >= target) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
参考资料:
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
我有这个示例代码: #include #include int main() { Eigen::MatrixXf M = Eigen::MatrixXf::Random(1000, 1000)
我有一个像这样的数据框: +-----+--------+ |count| country| +-----+--------+ | 12| Ireland| | 5|Thailand| +-
我想要 SUM(tot_bill_1+tot_bill_2) AS 总计,但这不起作用 SELECT *, IF(SUM(bill_1) IS NULL, '99', SUM(bill_1)) AS
如果我们有两个矩阵 X 和 Y,都是二维的,现在在数学上我们可以说:sum(X-Y)=sum(X)-总和(Y). Matlab 哪个效率更高?哪个更快? 最佳答案 在我的机器上,sum(x-y) 对于
我正在运行 Hive 1.1.0 并看到对于两个 bigint 列,active_users 和 inactive_users,SUM(active_users + inactive_users) <
是否可以在一个选择查询中求和? 类似这样的事情: SELECT id, SUM(current_price - bought_price)*amount AS profit FROM purchase
这是一个相当奇怪的结果。我希望这些具有相同的产量。 下面还有从数据库中提取的 excel 链接。 https://twentius.opendrive.com/files?89038281_muoyg
我必须对 2 个字段求和,然后再求和。从性能的角度来看,先添加字段还是在对列求和之后添加字段有什么区别? 方法 1 = SELECT SUM(columnA + columnB) 方法 2 = SEL
这是一个经典问题,但我很好奇是否有可能在这些条件下做得更好。 问题:假设我们有一个长度为4*N的排序数组,即每个元素重复4次。请注意,N 可以是任何自然数。此外,数组中的每个元素都受制于 0 A. 执
我正在编写一个 Pig 程序,该程序加载一个用制表符分隔整个文件的文件 例如:名称 TAB 年份 TAB 计数 TAB... file = LOAD 'file.csv' USING PigStora
我有一个包含以下字段的表: EmpID, Code, Amount, TransDate, CM, CMDate 我想要进入数据网格的是 SUM所有的Amount具有相同的 Code和 SUM CM具
我有两个单独的查询用于提取报告信息。一年效果很好。但是,如果一个月超过 1 年,则不会显示正确的响应。 这是我的两个查询: select SUM(rpt_complete.total) total,
我想查询一个团队的积分。通过在列上执行 SUM + 来自具有相同团队 ID 的另一个表的 SUM 来添加这些点。我试着这样写: SELECT k.id, s.fylke, s.
这个问题在这里已经有了答案: How to deal with floating point number precision in JavaScript? (47 个回答) Unexpected
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 这个问题似乎与 help center 中定义的范围内的编程无关。 . 关闭 5 年前。 Improve
我已经找了一段时间,但找不到这个问题的答案(也许我没有搜索正确的术语或其他东西)。基本上,我有一个数据库,每个日期有任意数量的条目。我需要取包含条目的最后 X 天的总和(忽略没有条目的天数)。我知道如
我正在尝试获取 B 行中包含 A 行中某个值的所有值中的一些值。我猜这个问题很简单。 这是我的查询: =QUERY('Sheet1'!$A$16:D, "Select sum(D) Where C c
我正在尝试运行以下查询,但出现以下错误: You have an error in your SQL syntax; check the manual that corresponds to your
我有一个 tableA,其中包含以下结构 我将此结构修改为如下所示的tableB,以减少行数,并且类别是固定长度的 假设我在 tableA 中修改为新结构后有 210 万条数据,tableB 仅包含
我的表在 Postgres 中的数据: id user_id sell_amount sell_currency_id buy_amount buy_currency_id type
我是一名优秀的程序员,十分优秀!