当前位置:网站首页>[算法] 剑指offer2 golang 面试题10:和为k的子数组
[算法] 剑指offer2 golang 面试题10:和为k的子数组
2022-07-06 09:18:00 【邓嘉文Jarvan】
[算法] 剑指offer2 golang 面试题10:和为k的子数组
题目1:
思路1: 暴力
时间复杂度 O(n2)
代码
func subarraySum(nums []int, k int) int {
//start: 13:51, 13:57
//思路1: 暴力,因为元素中有可能是负数
//固定一个数字i,记录后面存在的可能性
//参数校验
if len(nums) == 0 {
return 0
}
//暴力
count := 0
for i := 0; i < len(nums); i++{
sum := 0
for j := i; j < len(nums); j++{
sum += nums[j]
if sum == k {
count ++
}
}
}
return count
}
测试1
思路2: 前缀和 + hashmap
因为有负数存在, 所以滑动窗口是不能用的
代码
func subarraySum(nums []int, k int) int {
//start: 13:51, 13:57
//思路2: 前缀和 + hashmap
//
//参数校验
if len(nums) == 0 {
return 0
}
//前缀和和+ hashmap
sumToCount := make(map[int]int)
sum,resCount := 0,0
sumToCount[0] = 1
for i := 0; i < len(nums); i ++{
sum += nums[i]
//存在 sum - sumOld = k,累加到结果中
resCount += sumToCount[sum - k]
sumToCount[sum] += 1
}
return resCount
}
测试
边栏推荐
- Easy to use shortcut keys in idea
- 音乐播放(Toggle && PlayerPrefs)
- [Offer18]删除链表的节点
- rtklib单点定位spp使用抗差估计遇到的问题及解决
- Conditional probability
- InnoDB dirty page refresh mechanism checkpoint in MySQL
- What are the functions and features of helm or terrain
- Unity3D基础入门之粒子系统(属性介绍+火焰粒子系统案例制作)
- 基于rtklib源码进行片上移植的思路分享
- MySQL replacement field part content
猜你喜欢
FairyGUI循環列錶
C programming exercise
First use of dosbox
第一人称视角的角色移动
FairyGUI复选框与进度条的组合使用
Mixed use of fairygui button dynamics
MySQL時間、時區、自動填充0的問題
rtklib单点定位spp使用抗差估计遇到的问题及解决
[Clickhouse kernel principle graphic explanation] about the collaborative work of partitioning, indexing, marking and compressed data
The service robots that have been hyped by capital and the Winter Olympics are not just a flash in the pan
随机推荐
Solution to the problem of automatic login in Yanshan University Campus Network
[offer18] delete the node of the linked list
Mysql database reports an error: row size too large (> 8126) Changing some columns to TEXT or BLOB or using ROW_ FORMAT=DY
[Offer29] 排序的循环链表
@The difference between Autowired and @resource
音乐播放(Toggle && PlayerPrefs)
FairyGUI增益BUFF数值改变的显示
Vulnhub target: hacknos_ PLAYER V1.1
Easy to use shortcut keys in idea
FGUI工程打包发布&导入Unity&将UI显示出来的方式
Force buckle 1189 Maximum number of "balloons"
(一)R语言入门指南——数据分析的第一步
Meanings and differences of PV, UV, IP, VV, CV
SSD technical features
Database course design: college educational administration management system (including code)
Esp8266 connect onenet (old mqtt mode)
Theoretical derivation of support vector machine
Mixed use of fairygui button dynamics
Naive Bayesian theory derivation
There is no red exclamation mark after SVN update