当前位置:网站首页>[algorithm] sword finger offer2 golang interview question 10: subarray with sum K
[algorithm] sword finger offer2 golang interview question 10: subarray with sum K
2022-07-06 12:51:00 【Deng Jiawen jarvan】
[ Algorithm ] The finger of the sword offer2 golang Interview questions 10: And for k Subarray
subject 1:
Ideas 1: violence
Time complexity O(n2)
Code
func subarraySum(nums []int, k int) int {
//start: 13:51, 13:57
// Ideas 1: violence , Because there may be negative numbers in elements
// Fix a number i, Record the possibility behind
// Parameter checking
if len(nums) == 0 {
return 0
}
// violence
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
}
test 1
Ideas 2: The prefix and + hashmap
Because there are negative numbers , Therefore, sliding windows cannot be used
Code
func subarraySum(nums []int, k int) int {
//start: 13:51, 13:57
// Ideas 2: The prefix and + hashmap
//
// Parameter checking
if len(nums) == 0 {
return 0
}
// Prefix and + hashmap
sumToCount := make(map[int]int)
sum,resCount := 0,0
sumToCount[0] = 1
for i := 0; i < len(nums); i ++{
sum += nums[i]
// There is sum - sumOld = k, Add to result
resCount += sumToCount[sum - k]
sumToCount[sum] += 1
}
return resCount
}
test
边栏推荐
- Servlet
- Office prompts that your license is not genuine pop-up box solution
- 抗差估计在rtklib的pntpos函数(标准单点定位spp)中的c代码实现
- [offer78] merge multiple ordered linked lists
- Database course design: college educational administration management system (including code)
- (core focus of software engineering review) Chapter V detailed design exercises
- JUC forkjoin and completable future
- Itext 7 生成PDF总结
- Unity3d, Alibaba cloud server, platform configuration
- Force buckle 1189 Maximum number of "balloons"
猜你喜欢
随机推荐
RTKLIB: demo5 b34f.1 vs b33
Excel导入,导出功能实现
[899] ordered queue
【RTKLIB 2.4.3 b34 】版本更新简介一
FairyGUI摇杆
燕山大学校园网自动登录问题解决方案
wsl常用命令
Office prompts that your license is not genuine pop-up box solution
GPS高程拟合抗差中误差的求取代码实现
Combination of fairygui check box and progress bar
Force buckle 1189 Maximum number of "balloons"
Meanings and differences of PV, UV, IP, VV, CV
idea问题记录
VLSM variable length subnet mask partition tips
Database table splitting strategy
FairyGUI增益BUFF數值改變的顯示
[算法] 剑指offer2 golang 面试题3:前n个数字二进制形式中1的个数
[算法] 剑指offer2 golang 面试题9:乘积小于k的子数组
Affichage du changement de valeur du Buff de gain de l'interface graphique de défaillance
[leetcode19]删除链表中倒数第n个结点