1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| struct Solution;
// @lc code=start
impl Solution {
/// ## 解题思路
/// - 前缀差+hashmap
/// 1. 设置 diff: 表示当前位置0,1次数的差值;
/// 2. 设置 hashmap, 记录最近一次(diff, i);
/// 3. 从左至右依次遍历序列, 如果为0, 则diff+=1, 否则, diff-=1;
/// 4. 如果 diff == 0, 则说明从开始到当前位置的连续子数组中0,1出现次数相等, 更新最大子数组长度;
/// 5. 否则diff不为0, 检查hashmap中当前diff是否有记录
/// 如果不存在, 则将当前(diff, i)记录到hashmap中;
/// 6. 如果存在, 则表明当前位置i到hashmap中记录的上一个当前diff位置last_i之间的连续子数组
/// 0,1出现次数相等, 更新最大连续子数组长度;
pub fn find_max_length(nums: Vec<i32>) -> i32 {
let mut map = std::collections::HashMap::new();
let mut max_len = 0;
let mut diff = 0; // 当前位置0,1的次数差
// 遍历nums
for i in 0..nums.len() {
// 计算差值diff
match nums[i] {
0 => diff += 1,
_ => diff -= 1,
}
// 如果diff为0, 则表示从0开始到当前位置的子数组0,1相等
if diff == 0 {
// 更新最大子数组长度
max_len = max_len.max((i as i32) + 1);
} else if !map.contains_key(&diff) {
// 否则, 如果当前差值diff在hashmap没有记录,
// 则记录到hashmap中
map.insert(diff, i);
} else {
// 否则, 如果当前差值在之前出现过(hashmap中记录了)
// 则当前位置i到hashmap中记录值之间的子数组的0,1出现的数量必定相等,
// 更新最大子数组长度
max_len = max_len.max((i - map.get(&diff).unwrap()) as i32);
}
}
max_len
}
}
// @lc code=end
|