【前缀和】LeetCode 560. 和为k的字数组

这篇具有很好参考价值的文章主要介绍了【前缀和】LeetCode 560. 和为k的字数组。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述

力扣560题,链接:https://leetcode.cn/problems/subarray-sum-equals-k

【前缀和】LeetCode 560. 和为k的字数组,算法分析与设计,leetcode,算法

方法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 前缀和优化

使用哈希表优化,存储存储每个前缀和出现的个数

遍历数组,计算每个位置的前缀和,并用哈希表存储每个前缀和出现的次数。在计算前缀和时,通过检查哈希表中是否存在前缀和为 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模板网!

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

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

相关文章

  • leetcode 1304. 和为零的 N 个不同整数

    题目描述 解题思路 执行结果 leetcode 1304. 和为零的 N 个不同整数. 题目描述 和为零的 N 个不同整数 给你一个整数 n,请你返回 任意 一个由 n 个 各不相同 的整数组成的数组,并且这 n 个数相加和为 0 。 示例 1: 输入:n = 5 输出:[-7,-1,1,3,4] 解释:这些数组也是正确的 [-5,-1,

    2024年02月11日
    浏览(39)
  • 【LeetCode热题100】【子串】和为 K 的子数组

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

    2024年01月19日
    浏览(44)
  • 【LeetCode】双指针求解和为s的两个数字

    Problem: 剑指 Offer 57. 和为s的两个数字 首先来讲解一下本题的思路 我们看到本题的意思很简单,就是去这个 nums 这个数组中进行寻找,如果找到了两个数相加之和为 target 的话,那构成一个结果集并返回 接下去我们来分析一下本题的思路 暴力解法 首先第一种,我们都会想到的

    2024年02月09日
    浏览(43)
  • 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日
    浏览(48)
  • 算法——前缀和之除自身以外数组的乘积、和为K的子数组、和可被K整除的子数组、连续数组、矩阵区域和

    这几道题对于我们前面讲过的一维、二维前缀和进行了运用,包含了面对特殊情况的反操作 目录 4.除自身以外数组的乘积 4.1解析 4.2题解 5.和为K的子数组 5.1解析 5.2题解 6.和可被K整除的子数组 6.1解析 6.2题解 7.连续数组 7.1题解 7.2题解 8.矩阵区域和 8.1解析 8.2题解 4.除自身以外

    2024年04月14日
    浏览(44)
  • leetCode 2915. 和为目标值的最长子序列的长度 + 动态规划 +01背包 + 空间优化 + 记忆化搜索 + 递推

    2915. 和为目标值的最长子序列的长度 - 力扣(LeetCode) 给你一个下标从  0  开始的整数数组  nums  和一个整数  target  。返回和为  target  的  nums  子序列中,子序列  长度的最大值  。如果不存在和为  target  的子序列,返回  -1  。 子序列  指的是从原数组中删除一些

    2024年02月06日
    浏览(43)
  • 【leetcode】前缀和

    内容摘抄自: 小而美的算法技巧:前缀和数组 | labuladong 的算法小抄 一维数组的前缀和 看这个  preSum  数组,若想求索引区间  [1, 4]  内的所有元素之和, 就可以通过  preSum[5] - preSum[1]  得出。 二维数组的前缀和 如leetcode 304: 注意任意子矩阵的元素和可以转化成它周边几

    2024年02月13日
    浏览(35)
  • leetcode14. 最长公共前缀

    题目 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串 “”。 解题方法: 1.首先找到数组中长度最短的数据,与数组第一个数进行交换(公共前缀的长度肯定不会大于列表中长度最短的字符串) 2.接着 因为求最长公共前缀,将数组第

    2024年01月21日
    浏览(48)
  • [Leetcode] 0014. 最长公共前缀

    点击上方,跳转至Leetcode 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串  \\\"\\\" 。 示例 1: 示例 2: 提示: 1 = strs.length = 200 0 = strs[i].length = 200 strs[i] 仅由小写英文字母组成 横向扫描:写一个longestCommonPrefix方法,用于返回两个字符串的

    2024年02月10日
    浏览(50)
  • 【leetcode】动态规划::前缀和

    标题:【leetcode】前缀和 @水墨不写bug 正文开始: 给定一个长度为n的数组a1​,a2​,....an​. 接下来有q次查询, 每次查询有两个参数l, r. 对于每个询问, 请输出al​+al+1​+....+ar​ 输入描述: 第一行包含两个整数n和q. 第二行包含n个整数, 表示a1​,a2​,....an​. 接下来q行,每行包含

    2024年04月11日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包