题目描述
力扣560题,链接:https://leetcode.cn/problems/subarray-sum-equals-k
方法1 暴力
暴力法,三重for循环,时间复杂度
O
(
N
3
)
O(N^3)
O(N3),会超时。
思路:两个for循环遍历起始位置和终止位置,第三个for遍历求解这段区间的和是否为k。
代码略。
方法2 暴力优化
在暴力法中我们发现会在很多重复计算,比如求前10个数据的和时只需要在前9个和的基础上加上第10个数,因此我们可以在遍历起始和终止位置时顺便求出这段区间的和,减少一个for循环。
时间复杂度 O ( N 2 ) O(N^2) O(N2)。
public int subarraySum(int[] nums, int k) {
int len = nums.length;
int res = 0;
for (int i = 0; i < len; i++) { // 起始位置
int s = 0; // 当前起始位置时,每个终止位置的和
for (int j = i; j < len; j++) { // 终止位置
s += nums[j];
if(s == k)res++; // 等于k,答案+1
}
}
return res;
}
方法3 前缀和
假如一数组num为[1,2,3,4],则其前缀和数组prefixSum为[0,1,3,6,10],表示数据num中每一项到数据第一项的和,其中前缀为空时的前缀和为0,即prefixSum[0] = 0。
prefixSum[0] = 0
prefixSum[1] = a0
prefixSum[2] = a0 + a1
prefixSum[3] = a0 + a1 + a2
连续数组a1、a2的和为prefixSum[3]-prefixSum[1]
连续数组a0、a1、a2的和为prefixSum[3]-prefixSum[0]
求连续字数组和为k的数量 转换为 求解前缀数组之差的数量。
因此,首先初始化前缀数组,然后依次求出前缀数组之差为k的数量。时间复杂度 O ( N 2 ) O(N^2) O(N2)。
public int subarraySum(int[] nums, int k) {
int len = nums.length;
int res = 0; // 最终答案
int[] preSum = new int[len+1]; // 前缀数组
preSum[0] = 0;
int s = 0;
for (int i = 0; i < len; i++) { // 前缀数组赋值
s+=nums[i];
preSum[i+1] = s;
}
/**
* 遍历前缀数组
* 注意:前缀数组的长度为原始数组长度+1,原数组长度
*
*/
for (int i = 1; i < len+1; i++) { // 从原数组nums第一个数据开始
for (int j = i; j < len+1; j++) {
if(preSum[j]-preSum[i-1]==k) res++;
}
}
return res;
}
方法4 前缀和优化
使用哈希表优化,存储存储每个前缀和出现的个数文章来源:https://www.toymoban.com/news/detail-605308.html
遍历数组,计算每个位置的前缀和,并用哈希表存储每个前缀和出现的次数。在计算前缀和时,通过检查哈希表中是否存在前缀和为 s-k 的记录,来找到以当前位置为结尾的子数组中和为 k 的子数组数量。时间复杂度 O ( N ) O(N) O(N)。文章来源地址https://www.toymoban.com/news/detail-605308.html
public int subarraySum(int[] nums, int k) {
int len = nums.length;
int res = 0; // 最终答案
HashMap<Integer, Integer> map = new HashMap<>(); // 利用字典存储前缀和以及对应个数
map.put(0,1); // 初始状态下,前缀和为0的有1个
int s = 0;// s :从0位置到i位置的和
for (int i = 0; i < len; i++) {
s += nums[i]; // 从0位置到i位置的和 为 s
if(map.containsKey(s-k)){ // 找出 前缀和为s-k 所对应的数量
res += map.get(s-k); // map.get(s-k)表示以当前位置为结尾的子数组中和为 k 的子数组数量
}
map.put(s,map.getOrDefault(s,0)+1); // 更新字典
}
return res;
}
到了这里,关于【前缀和】LeetCode 560. 和为k的字数组的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!