数组：子数组
# 0209. 长度最小的子数组 (opens new window)
题目
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 nums[l], nums[l+1], ..., nums[r-1], nums[r] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
解析
滑动窗口，外层 for 循环负责更新右边界，内层 while 循环负责更新左边界，遇到满足条件的区间则更新最小长度值。
代码
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int ans = INT_MAX;
int left = 0, sum = 0;
for (int i = 0; i < nums.size(); i ++) {
sum += nums[i];
while (left <= i && sum >= target) {
ans = min(ans, i - left + 1);
sum -= nums[left++];
}
}
return ans == INT_MAX ? 0 : ans;
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 0238. 除自身以外数组的乘积 (opens new window)
题目
给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
解析
两次遍历，分别计算每个位置左侧所有元素的乘积和右侧所有元素的乘积，遍历结束返回即可。
代码
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> ans(nums.size());
ans[0] = 1;
for (int i = 1; i < nums.size(); i ++) {
ans[i] = ans[i - 1] * nums[i - 1];
}
int right = 1;
for (int i = nums.size() - 1; i >= 0; i --) {
ans[i] *= right;
right *= nums[i];
}
return ans;
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 0325. 和等于 k 的最长子数组长度 (opens new window)
题目
给定一个数组 nums 和一个目标值 k，找到和等于 k 的最长子数组长度。如果不存在任意一个符合要求的子数组，则返回 0。
注意：nums 数组的总和是一定在 32 位有符号整数范围之内的。
解析
首先构建前缀和，之后遍历数组，通过 Hash 表查找满足条件的前缀和索引，更新最大的子数组长度。
代码
class Solution {
public:
int maxSubArrayLen(vector<int>& nums, int k) {
if (nums.empty()) return 0;
int ans = 0;
unordered_map<int, int> record;
record[0] = -1;
for (int i = 1; i < nums.size(); i ++) {
nums[i] += nums[i - 1];
}
for (int i = 0; i < nums.size(); i ++) {
if (record.find(nums[i] - k) != record.end()) {
ans = max(ans, i - record[nums[i] - k]);
}
if (record.find(nums[i]) == record.end()) {
record[nums[i]] = i;
}
}
return ans;
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 0523. 连续的子数组和 (opens new window)
题目
给定一个包含 非负数 的数组和一个目标 整数 k ，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，且总和为 k 的倍数，即总和为 n * k ，其中 n 也是一个整数。
解析
若存在两个子数组满足以下条件：
则存在：
因此，可使用前缀和与 k 的模作为键，值为对应的数组下标，若存在两个相同模的前缀和下标，且下标间距大于 1，则满足子数组条件。
代码
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
int sum = 0;
unordered_map<int, int> record;
record[0] = -1;
for (int i = 0; i < nums.size(); i ++) {
sum += nums[i];
if (k != 0) sum %= k;
if (record.find(sum) != record.end()) {
if (i - record[sum] > 1) {
return true;
}
} else {
record[sum] = i;
}
}
return false;
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 0548. 将数组分割成和相等的子数组 (opens new window)
题目
给定一个有 n 个整数的数组，你需要找到满足以下条件的三元组 (i, j, k) ：
- 0 < i, i + 1 < j, j + 1 < k < n - 1
- 子数组 (0, i - 1)，(i + 1, j - 1)，(j + 1, k - 1)，(k + 1, n - 1) 的和应该相等。
这里我们定义子数组 (L, R) 表示原数组从索引为L的元素开始至索引为R的元素。
解析
首先计算前缀和，之后枚举 j 的位置，根据 j 的位置寻找满足条件的 i 和 k 的位置即可。
代码
class Solution {
public:
bool splitArray(vector<int>& nums) {
if (nums.size() < 7) {
return false;
}
vector<int> sum(nums.size());
sum[0] = nums[0];
for (int i = 1; i < nums.size(); i ++) {
sum[i] = sum[i - 1] + nums[i];
}
for (int j = 3; j < nums.size() - 3; j ++) {
unordered_set<int> record;
for (int i = 1; i < j - 1; i ++) {
if (sum[i - 1] == sum[j - 1] - sum[i]) {
record.insert(sum[i - 1]);
}
}
for (int k = j + 2; k < nums.size() - 1; k ++) {
if (sum[nums.size() - 1] - sum[k] == sum[k - 1] - sum[j] &&
record.find(sum[k - 1] - sum[j]) != record.end()) {
return true;
}
}
}
return false;
}
};
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
# 0560. 和为K的子数组 (opens new window)
题目
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
解析
在计算前缀和的同时，维护一个 Hash 表，存储每个前缀和的子数组个数，每次循环检查表中是否存在满足条件的前缀和，累加结果即可。
代码
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int ans = 0;
int sum = 0;
unordered_map<int, int> record;
record[0] = 1;
for (int i = 0; i < nums.size(); i ++) {
sum += nums[i];
if (record.find(sum - k) != record.end()) {
ans += record[sum - k];
}
record[sum] += 1;
}
return ans;
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17