和为 K 的子数组(java)

server/2024/11/23 22:46:27/

题目描述:

给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数 

子数组是数组中元素的连续非空序列

示例 1:

输入:nums = [1,1,1], k = 2
输出:2

示例 2:

输入:nums = [1,2,3], k = 3
输出:2

代码思路: 

class Solution {public int subarraySum(int[] nums, int k) {int sum = 0;int count = 0;for(int i=0;i<nums.length;i++){sum = nums[i];if(sum==k){count++;}int j=i+1;while(j<nums.length){sum = sum+nums[j];if(sum==k){count++;}j++;}}return count;}
}

官方思路

解题方案一:

public class Solution {public int subarraySum(int[] nums, int k) {int count = 0;for (int start = 0; start < nums.length; ++start) {int sum = 0;for (int end = start; end >= 0; --end) {sum += nums[end];if (sum == k) {count++;}}}return count;}
}

 

解题方案二:

使用前缀和的方法可以解决这个问题,因为我们需要找到和为k的连续子数组的个数。通过计算前缀和,我们可以将问题转化为求解两个前缀和之差等于k的情况。

假设数组的前缀和数组为prefixSum,其中prefixSum[i]表示从数组起始位置到第i个位置的元素之和。那么对于任意的两个下标i和j(i < j),如果prefixSum[j] - prefixSum[i] = k,即从第i个位置到第j个位置的元素之和等于k,那么说明从第i+1个位置到第j个位置的连续子数组的和为k。

通过遍历数组,计算每个位置的前缀和,并使用一个哈希表来存储每个前缀和出现的次数。在遍历的过程中,我们检查是否存在prefixSum[j] - k的前缀和,如果存在,说明从某个位置到当前位置的连续子数组的和为k,我们将对应的次数累加到结果中。

这样,通过遍历一次数组,我们可以统计出和为k的连续子数组的个数,并且时间复杂度为O(n),其中n为数组的长度。

public class Solution {
public static int subarraySum(int[] nums, int k) {int count = 0;int sum = 0;Map<Integer, Integer> map = new HashMap<>();map.put(0, 1); // 初始化前缀和为0的次数为1for (int i = 0; i < nums.length; i++) {sum += nums[i];if (map.containsKey(sum - k)) {count += map.get(sum - k);}map.put(sum, map.getOrDefault(sum, 0) + 1);}return count;}
}


http://www.ppmy.cn/server/144378.html

相关文章

LSTM原理解读与实战

在RNN详解及其实战中&#xff0c;简单讨论了为什么需要RNN这类模型、RNN的具体思路、RNN的简单实现等问题。同时&#xff0c;在文章结尾部分我们提到了RNN存在的梯度消失问题&#xff0c;及之后的一个解决方案&#xff1a;LSTM。因此&#xff0c;本篇文章主要结构如下&#xff…

Easyexcel(2-文件读取)

相关文章链接&#xff1a; Easyexcel&#xff08;1-注解使用&#xff09;Easyexcel&#xff08;2-文件读取&#xff09; 同步读取 读取单个Sheet 通过sheet方法指定对应的Sheet名称或下标读取文件信息通过doReadSync方法实现同步读取 Data public class UserExcel {ExcelI…

项目中排查bug的思路案例

bug描述&#xff1a;调用了删除的接口&#xff0c;执行成功了&#xff0c;也删掉了选中的数据&#xff0c;但是不执行删除后的处理操作&#xff0c;会报一个“系统未知错误&#xff0c;请反馈给管理员” 解决&#xff1a; 成功删掉了数据&#xff0c;但删除后的操作没有执行&a…

Docker 容器自动启动设置

在 Docker 中&#xff0c;可以通过设置容器的重启策略来实现容器的自动启动。这意味着&#xff0c;当 Docker 守护进程启动时&#xff0c;它可以自动启动特定的容器&#xff0c;无论是因为系统重启还是 Docker 服务本身的重启。 设置容器自动启动 要设置容器自动启动&#xf…

ElasticSearch学习笔记四:基础操作(二)

一、前言 上一篇文章中我们学习了ES中的基础操作&#xff0c;包括索引和映射&#xff0c;同时也学习了ES中的基础数据类型&#xff0c;今天我们继续学习其他的数据类型。 二、复杂数据类型 1、数组&#xff08;Array&#xff09; 在ES中没有特别指定数据类型&#xff0c;换…

C++ String

C中的字符串详解 在C中&#xff0c;字符串处理是一个重要的编程主题。字符串是一种用于存储文本数据的对象&#xff0c;C为字符串提供了丰富的操作接口&#xff0c;使得处理字符串变得灵活而高效。本文将详细介绍C的字符串&#xff0c;包括其定义、创建方式、操作技巧以及相关…

介绍一下strncmp(c基础)

strncmp是strcmp的进阶版 链接介绍一下strcmp(c基础)-CSDN博客 作用 比较两个字符串的前n位 格式 #include <string.h> strncmp (arr1,arr2,n); 工作原理&#xff1a;strcmp函数按照ACII&#xff08;字符编码顺序&#xff09;比较两个字符串。它从两个字符串的第一…

FreeRTOS——信号量

目录 一、概念及其应用 1.1定义 1.2作用 二、二值信号量 2.1定义 2.2二值信号量工作机制 2.3二值信号量应用场景—同步 2.4二值信号量API 2.4.1创建二值信号量 2.4.2任务中释放信号量 2.4.3中断中释放信号量 2.4.4任务中获取信号量 2.4.5中断中获取信号量 三、计…