128、最长连续序列
题目说明
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
解题思路1：排序
此法不满足时间复杂度为O(n)
先对数组进行排序，当遇到不连续的数时则重置当前的序列长度为1，遇到与前一位置相同的数时则跳过
解题思路2：哈希
首先对数组的数据进行处理，将其保留到HashSet中同时还起到了对数据去重的效果
然后再对数组进行遍历，用变量cur来记录当前的数值并进入while循环中，反复比对set中是否包含cur + 1并不断更新最终长度max_length。
为了减少遍历的时间，在主循环的遍历中可以判定nums[i - 1]是否包含在set中，如果包含的话说明以当前数为起点的序列肯定是以nums[i - 1]开头的子序列，没有再进入while去set中匹配的意义。
3、无重复字符的最长子串
题目说明
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
解题思路
维护一个窗口，用HashSet记录下窗口中出现的值。如果index = right的值还未出现，窗口可以向右移动；如果出现了则说明左边已经出现过，left慢慢右移并remove掉对应的值
560、和为 K 的子数组
题目说明
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。
输入：nums = [1,1,1], k = 2
输出：2
解题思路：前缀和&哈希
此题需要转换一下思维，易知目标是nums[i ~ j]的区间和是k，那么说明pre[j] - pre[i - 1] = k，即pre[j] - k = pre[i - 1]，由此可知满足条件时之前的前缀和就已经出现过了，因此我们可以将前缀和及其出现的次数记录下来，便可获得最终的结果。
首先要对HashSet初始化，因为当pre[j] - k如果等于0的话自然是符合结果的，因此要先往HashSet中加入(0, 1)对。此后不断的加入(pre, map.getOrDefault(pre, 0) + 1)，在过程中不断的判断pre - k是否出现过并记录结果
核心代码如下
for (int i = 0; i < nums.length; i++) {
pre += nums[i];
if (map.containsKey(pre - k)) {
res += map.get(pre - k);
}
map.put(pre, map.getOrDefault(pre, 0) + 1);
}
238、除自身以外数组的乘积
题目说明
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请不要使用除法，且在 O(n) 时间复杂度内完成此题。
解题思路
因为要求不用除法，整体乘积可以拆分成三个部分：left[i] * nums[i] * right[i] = product，问题转换成求出left[i]与``right[i]，而left[i]与right[i]可以分别通过前缀和后缀得到：
每一个数的前缀乘积都是基于此前的上一个前缀乘积 *上一个数，后缀乘积也是同理left[i] = left[i - 1] * nums[i - 1];``right[i] = right[i + 1] * nums[i + 1];汇总即可获得最终结果
如果要在O(1)的空间来获得结果的话，则不用left和right数组，首先将left数组的遍历方式结果直接存储在answer中，然后设定一个变量right，通过其自右向左遍历，不断乘nums[i + 1]并乘到answer[i]中即可
标签：pre,right,20230421,前缀,nums,数组,100,热题,left From： https://www.cnblogs.com/xccx-0824/p/17342550.html