当前位置:网站首页>【无标题】
【无标题】
2022-07-06 09:18:00 【邓嘉文Jarvan】
[算法] 剑指offer2 golang 0和1个数相同的子数组
题目1:
思路1: 暴力
//思路1: 暴力
//将0当作-1看待,
//固定一个,计算后面的位数是否总和位0,计算最大的个数,
//O(n3),优化下计算时间复杂度O(n2)
代码1
func findMaxLength(nums []int) int {
//返回最长的子数组的长度
//start :19.11
//思路1: 暴力
//将0当作-1看待,
//固定一个,计算后面的位数是否总和位0,计算最大的个数,
//O(n3),优化下计算时间复杂度O(n2)
//参数处理
if len(nums) == 0 {
return 0
}
//暴力
max := 0
for i := 0; i < len(nums) - 1; i++ {
//左指针
sum := 1
if nums[i] == 0 {
sum = -1
}
for j := i+1; j < len(nums); j++{
if nums[j] == 0 {
sum--
}else {
sum++
}
// 符合条件刷新最大值 max
temp := j - i +1
if sum == 0 && temp > max{
max = temp
}
}
}
return max
}
测试1
思路2: hashmap
//1.使用 hashmap[sum]index 记录前 n 个元素和位 sum 的下标,如果后面的元素 sum2
//如果 sum2 - sum1 = 0, sum2 = sum1,证明存在就取之前的 value
代码2:
func findMaxLength(nums []int) int {
//返回最长的子数组的长度
//start :19.26
//思路2: hashmap
//1.使用 hashmap[sum]index 记录前 n 个元素和位 sum 的下标,如果后面的元素 sum2
//如果 sum2 - sum1 = 0, sum2 = sum1,证明存在就取之前的 value
if len(nums) == 0 {
return 0
}
//1.hashmap 赋值
hashmap := make(map[int]int)
//处理边界
hashmap[0] = -1
sum1,max := 0,0
for i := 0; i < len(nums); i++ {
if nums[i] == 0 {
sum1 --
}else {
sum1 ++
}
if val,ok := hashmap[sum1]; ok {
length := i - val
if length > max {
max = length
}
}else {
//只是保留小index的,大的不需要
hashmap[sum1] = i
}
}
return max
}
边栏推荐
- Gateway fails to route according to the service name, and reports an error service unavailable, status=503
- [offer9]用两个栈实现队列
- GNSS定位精度指标计算
- NRF24L01 troubleshooting
- [899] ordered queue
- [offer29] sorted circular linked list
- Fairygui gain buff value change display
- [leetcode19] delete the penultimate node in the linked list
- FairyGUI简单背包的制作
- [offer9] implement queues with two stacks
猜你喜欢
Guided package method in idea
【干货】提升RTK模糊度固定率的建议之周跳探测
ORA-02030: can only select from fixed tables/views
Unity场景跳转及退出
单片机蓝牙无线烧录
(core focus of software engineering review) Chapter V detailed design exercises
Affichage du changement de valeur du Buff de gain de l'interface graphique de défaillance
Fairygui joystick
FairyGUI循環列錶
(3) Introduction to bioinformatics of R language - function, data Frame, simple DNA reading and analysis
随机推荐
Flink late data processing (3)
There is no red exclamation mark after SVN update
1041 be unique (20 points (s)) (hash: find the first number that occurs once)
Matlab读取GNSS 观测值o文件代码示例
【GNSS数据处理】赫尔默特(helmert)方差分量估计解析及代码实现
Database course design: college educational administration management system (including code)
Servlet
(the first set of course design) 1-4 message passing interface (100 points) (simulation: thread)
Conditional probability
微信小程序开发心得
SVN更新后不出现红色感叹号
(3) Introduction to bioinformatics of R language - function, data Frame, simple DNA reading and analysis
Force buckle 1189 Maximum number of "balloons"
[899] ordered queue
FairyGUI复选框与进度条的组合使用
CUDA C programming authoritative guide Grossman Chapter 4 global memory
KF UD分解之UD分解基础篇【1】
FairyGUI增益BUFF数值改变的显示
FGUI工程打包发布&导入Unity&将UI显示出来的方式
【rtklib】在rtk下使用抗差自适应卡尔曼滤波初步实践