🔥 个人主页: 黑洞晓威
😀你不必等到非常厉害，才敢开始，你需要开始，才会变的非常厉害

2007. 从双倍数组中还原原数组

一个整数数组 original 可以转变成一个 双倍 数组 changed ，转变方式为将 original 中每个元素 值乘以 2 加入数组中，然后将所有元素 随机打乱 。

给你一个数组 changed ，如果 change 是 双倍 数组，那么请你返回 original数组，否则请返回空数组。original 的元素可以以 任意 顺序返回。

示例 1：

输入：changed = [1,3,4,2,6,8]
输出：[1,3,4]
解释：一个可能的 original 数组为 [1,3,4] :
- 将 1 乘以 2 ，得到 1 * 2 = 2 。
- 将 3 乘以 2 ，得到 3 * 2 = 6 。
- 将 4 乘以 2 ，得到 4 * 2 = 8 。
其他可能的原数组方案为 [4,3,1] 或者 [3,1,4] 。

解题思路

首先把 changed\textit{changed}changed 排序，并且统计所有元素出现的频数。

然后我们从小到大依次遍历数组，如果对于一个元素，它的频数大于零，并且它的两倍数也还在数组中，我们则可以把它加入到答案中。

如果对于一个数找不到它两倍数，即两倍数的频数等于零，则说明无法找到原数组，返回空数组即可。

代码实现

class Solution {public int[] findOriginalArray(int[] changed) {Arrays.sort(changed);Map<Integer, Integer> count = new HashMap<>();for (int a : changed) {count.put(a, count.getOrDefault(a, 0) + 1);}int[] res = new int[changed.length / 2];int i = 0;for (int a : changed) {if (count.get(a) == 0) {continue;}count.put(a, count.get(a) - 1);if (count.getOrDefault(a * 2, 0) == 0) {return new int[0];}count.put(a * 2, count.get(a * 2) - 1);res[i++] = a;}return res;}
}

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解题思路

1. 初始化一个 HashMap 用于存储字符和字符的最新出现的位置。HashMap 的 key 存储字符，value 存储字符下标。
2. 使用双指针 left 和 right 表示当前子串的左右边界，left 表示窗口的起始位置，right 是窗口的结束位置。
3. 遍历整个字符串，对于字符串中的每个字符：
   • 如果字符已经在 HashMap 中，更新 left 指针的位置为该字符在 HashMap 中出现的位置加 1。
   • 更新该字符在 HashMap 中的位置为当前的位置。
   • 计算当前窗口的长度 right - left + 1 并更新最大长度 max。
4. 最终返回最大长度 max 即为最长的不含重复字符的子串长度。

代码实现

import java.util.HashMap;class Solution {public int lengthOfLongestSubstring(String s) {if (s.length() == 0) return 0;HashMap<Character, Integer> map = new HashMap<>();int max = 0;int left = 0;for (int right = 0; right < s.length(); right++) {if (map.containsKey(s.charAt(right))) {left = Math.max(left, map.get(s.charAt(right)) + 1);}map.put(s.charAt(right), right);max = Math.max(max, right - left + 1);}return max;}
}