996 保险
最近，有网友爆料，在自己公司楼下，遇到了保险销售人员推销一款名为"996奋斗无忧险"的险种。
该宣传册介绍其为"熬夜险"、"奋斗无忧意外险"，缴费为 18 元起/年，赔偿方面，为"最高60万，猝死/意外/救护车"，牌子下方落款为"中国平安"。
后来有记者找中国平安确认此事，得到答复是：该保险可能是第三方和中国平安联合推出的产品，目前官方商城并无售卖此产品。
比 996 更可悲的是，996 都能出保险了。
你要知道，不合法的东西，是不能承保的，就好像没有保险会为「抢劫的结果」进行承保。
对此，你还能怎么看？欢迎评论区交流。
...
回归主题。
来一道和「美团」相关的算法题。
题目描述
平台：LeetCode
题号：525
给定一个二进制数组 nums , 找到含有相同数量的 和 的最长连续子数组，并返回该子数组的长度。
示例 1:
输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量0和1的最长连续子数组。
示例 2:
输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。
提示：
nums[i]不是 就是
前缀和 + 哈希表
根据题意，我们可以轻易发现如下性质：如果答案非 ，那么子数组长度必然为偶数，且长度至少为 。
具体的，我们在预处理前缀和时，将 为 的值当做 处理。
从而将问题转化为：「如何求得最长一段区间和为 的子数组」。同时使用「哈希表」来记录「某个前缀和出现的最小下标」是多少。
Java 代码：
class Solution {
public int findMaxLength(int[] nums) {
int n = nums.length, ans = 0;
int[] sum = new int[n + 10];
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (nums[i - 1] == 0 ? -1 : 1);
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 0);
for (int i = 1; i <= n; i++) {
int t = sum[i];
if (map.containsKey(t)) ans = Math.max(ans, i - map.get(t));
if (!map.containsKey(t)) map.put(t, i);
}
return ans;
}
}
C++ 代码：
class Solution {
public:
int findMaxLength(vector<int>& nums) {
int n = nums.size(), ans = 0;
vector<int> sum(n + 1, 0);
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + (nums[i - 1] == 0 ? -1 : 1);
}
unordered_map<int, int> map;
map[0] = 0;
for (int i = 1; i <= n; i++) {
int t = sum[i];
if (map.count(t)) ans = max(ans, i - map[t]);
if (!map.count(t)) map[t] = i;
}
return ans;
}
};
Python 代码：
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
n, ans = len(nums), 0
sumv = [0] * (n + 1)
for i in range(1, n + 1):
sumv[i] = sumv[i - 1] + (-1 if nums[i - 1] == 0 else 1)
mapping = {0: 0}
for i in range(1, n + 1):
t = sumv[i]
if t in mapping:
ans = max(ans, i - mapping[t])
if t not in mapping:
mapping[t] = i
return ans
TypeScript 代码：
function findMaxLength(nums: number[]): number {
let n = nums.length, ans = 0
const sum = new Array<number>(n + 10).fill(0)
for (let i = 1; i <= n; i++) sum[i] = sum[i - 1] + (nums[i - 1] == 0 ? -1 : 1)
const map = new Map<number, number>()
map.set(0, 0)
for (let i = 1; i <= n; i++) {
const t = sum[i]
if (map.has(t)) ans = Math.max(ans, i - map.get(t))
if (!map.has(t)) map.set(t, i)
}
return ans
};
时间复杂度： 空间复杂度：
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
