牛客NC343 和大于等于K的最短子数组【困难 前缀和 Java/Go】

2024-05-12 15:28

本文主要是介绍牛客NC343 和大于等于K的最短子数组【困难 前缀和 Java/Go】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

在这里插入图片描述
题目链接:
https://www.nowcoder.com/practice/3e1fd3d19fb0479d94652d49c7e1ead1

思路

本答案利用前缀和解答,Java,Go答案通过,但是同样的代码用PHP的话有一个测试用例超时
应该还有更优秀的答案,后面找到更优答案再更新博客

Java代码

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param nums int整型ArrayList* @param k int整型* @return int整型*/public int shortestSubarray (ArrayList<Integer> nums, int k) {//前缀和int n = nums.size();int[] sum = new int[n + 1];for (int i = 0; i < n; i++) {sum[i + 1] = sum[i] + nums.get(i);sum[i + 1]%=1000000007;  //关键if (nums.get(i) == k) return 1;}int ans = 0x7fffffff;for (int i = 0; i <= n ; i++) {if (sum[i] >= k) {ans = Math.min(ans, i);for (int j = i ; j >= 0 ; j--) {int diff = sum[i] - sum[j];if (diff >= k) {ans = Math.min(ans, i - j);break;}}}}if (ans == 0x7fffffff)return -1;return ans;}
}

Go代码

package main/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param nums int整型一维数组* @param k int整型* @return int整型*/
func shortestSubarray(nums []int, k int) int {//前缀和n := len(nums)ans := 0x7fffffffsum := make([]int, n+1)for i := 0; i < n; i++ {sum[i+1] = sum[i] + nums[i]if nums[i] == k {return 1}}for i := 0; i <= n; i++ {if sum[i] >= k { //剪枝if sum[i] >= k {if i < ans {ans = i}}for j := i; j >= 0; j-- {diff := sum[i] - sum[j]if diff >= k {if i-j < ans {ans = i - j}break}}}}if ans == 0x7fffffff {return -1}return ans
}

这篇关于牛客NC343 和大于等于K的最短子数组【困难 前缀和 Java/Go】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/983002

相关文章

SpringBoot使用Apache Tika检测敏感信息

《SpringBoot使用ApacheTika检测敏感信息》ApacheTika是一个功能强大的内容分析工具,它能够从多种文件格式中提取文本、元数据以及其他结构化信息,下面我们来看看如何使用Ap... 目录Tika 主要特性1. 多格式支持2. 自动文件类型检测3. 文本和元数据提取4. 支持 OCR(光学

Java内存泄漏问题的排查、优化与最佳实践

《Java内存泄漏问题的排查、优化与最佳实践》在Java开发中,内存泄漏是一个常见且令人头疼的问题,内存泄漏指的是程序在运行过程中,已经不再使用的对象没有被及时释放,从而导致内存占用不断增加,最终... 目录引言1. 什么是内存泄漏?常见的内存泄漏情况2. 如何排查 Java 中的内存泄漏?2.1 使用 J

JAVA系统中Spring Boot应用程序的配置文件application.yml使用详解

《JAVA系统中SpringBoot应用程序的配置文件application.yml使用详解》:本文主要介绍JAVA系统中SpringBoot应用程序的配置文件application.yml的... 目录文件路径文件内容解释1. Server 配置2. Spring 配置3. Logging 配置4. Ma

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu

java脚本使用不同版本jdk的说明介绍

《java脚本使用不同版本jdk的说明介绍》本文介绍了在Java中执行JavaScript脚本的几种方式,包括使用ScriptEngine、Nashorn和GraalVM,ScriptEngine适用... 目录Java脚本使用不同版本jdk的说明1.使用ScriptEngine执行javascript2.

Go语言实现将中文转化为拼音功能

《Go语言实现将中文转化为拼音功能》这篇文章主要为大家详细介绍了Go语言中如何实现将中文转化为拼音功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 有这么一个需求:新用户入职 创建一系列账号比较麻烦,打算通过接口传入姓名进行初始化。想把姓名转化成拼音。因为有些账号即需要中文也需要英

Spring MVC如何设置响应

《SpringMVC如何设置响应》本文介绍了如何在Spring框架中设置响应,并通过不同的注解返回静态页面、HTML片段和JSON数据,此外,还讲解了如何设置响应的状态码和Header... 目录1. 返回静态页面1.1 Spring 默认扫描路径1.2 @RestController2. 返回 html2

Spring常见错误之Web嵌套对象校验失效解决办法

《Spring常见错误之Web嵌套对象校验失效解决办法》:本文主要介绍Spring常见错误之Web嵌套对象校验失效解决的相关资料,通过在Phone对象上添加@Valid注解,问题得以解决,需要的朋... 目录问题复现案例解析问题修正总结  问题复现当开发一个学籍管理系统时,我们会提供了一个 API 接口去

Java操作ElasticSearch的实例详解

《Java操作ElasticSearch的实例详解》Elasticsearch是一个分布式的搜索和分析引擎,广泛用于全文搜索、日志分析等场景,本文将介绍如何在Java应用中使用Elastics... 目录简介环境准备1. 安装 Elasticsearch2. 添加依赖连接 Elasticsearch1. 创

Spring核心思想之浅谈IoC容器与依赖倒置(DI)

《Spring核心思想之浅谈IoC容器与依赖倒置(DI)》文章介绍了Spring的IoC和DI机制,以及MyBatis的动态代理,通过注解和反射,Spring能够自动管理对象的创建和依赖注入,而MyB... 目录一、控制反转 IoC二、依赖倒置 DI1. 详细概念2. Spring 中 DI 的实现原理三、