当前位置:网站首页>[算法] 剑指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
}
测试
边栏推荐
- [offer78] merge multiple ordered linked lists
- (4) Data visualization of R language -- matrix chart, histogram, pie chart, scatter chart, linear regression and strip chart
- How to add music playback function to Arduino project
- Programming homework: educational administration management system (C language)
- idea中导包方法
- Agile development helps me
- Office prompts that your license is not genuine pop-up box solution
- C programming exercise
- The service robots that have been hyped by capital and the Winter Olympics are not just a flash in the pan
- JS Title: input array, exchange the largest with the first element, exchange the smallest with the last element, and output array.
猜你喜欢
Teach you to release a DeNO module hand in hand
Halcon knowledge: gray_ Tophat transform and bottom cap transform
Vulnhub target: hacknos_ PLAYER V1.1
Design and implementation of general interface open platform - (39) simple and crude implementation of API services
Lock wait timeout exceeded try restarting transaction
(4) Data visualization of R language -- matrix chart, histogram, pie chart, scatter chart, linear regression and strip chart
NRF24L01故障排查
Combination of fairygui check box and progress bar
FairyGUI摇杆
CUDA C programming authoritative guide Grossman Chapter 4 global memory
随机推荐
(四)R语言的数据可视化——矩阵图、柱状图、饼图、散点图与线性回归、带状图
1041 Be Unique (20 point(s))(哈希:找第一个出现一次的数)
Meanings and differences of PV, UV, IP, VV, CV
Flink late data processing (3)
Programming homework: educational administration management system (C language)
MySQL time, time zone, auto fill 0
[leetcode19]删除链表中倒数第n个结点
Introduction to the daily practice column of the Blue Bridge Cup
Solution to the problem of automatic login in Yanshan University Campus Network
【rtklib】在rtk下使用抗差自适应卡尔曼滤波初步实践
Remember an experience of ECS being blown up by passwords - closing a small black house, changing passwords, and changing ports
Office提示您的许可证不是正版弹框解决
[Yu Yue education] guide business reference materials of Wuxi Vocational and Technical College of Commerce
Acwing-116 pilot brother
Fabrication of fairygui simple Backpack
Unity3D,阿里云服务器,平台配置
(课设第一套)1-5 317号子任务 (100 分)(Dijkstra:重边自环)
Office prompts that your license is not genuine pop-up box solution
[Offer18]删除链表的节点
Special palindromes of daily practice of Blue Bridge Cup