每日算法-250521

每日算法学习

大家好！这是我今天的算法练习记录，分享四道 LeetCode 题目的解题思路和代码。希望能对大家有所帮助！

---

219. 存在重复元素 II

题目

思路

哈希表

利用哈希表来存储数组中元素及其最近出现的索引。

解题过程

当我们遍历数组 nums 到元素 nums[i] 时：

1. 检查哈希表 map 中是否已存在 nums[i]。
2. 如果存在，说明之前遇到过相同的元素。设其之前的索引为 j = map.get(nums[i])。
3. 判断当前索引 i 与之前索引 j 的差的绝对值是否小于等于 k，即 abs(i - j) <= k (由于我们是从左到右遍历，i 总是大于 j，所以 i - j <= k)。如果满足条件，则返回 true。
4. 无论是否满足上述条件，都需要更新（或插入）nums[i] 在哈希表中的索引为当前的 i，以确保我们总是记录的是元素最近一次出现的索引。
5. 如果遍历完整个数组都没有找到符合条件的两个元素，则返回 false。

复杂度

• 时间复杂度: $O(N)$, 其中 N 是数组 nums 的长度。我们只需要遍历数组一次。哈希表的插入和查找操作平均时间复杂度为 $O(1)$。
• 空间复杂度: $O(\min (N,M))$, 其中 N 是数组的长度，M 是数组中不同元素的个数。最坏情况下，所有元素都不同，哈希表需要存储 N 个元素。

Code

class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {if (map.containsKey(nums[i])) {if (i - map.get(nums[i]) <= k) {return true;}}map.put(nums[i], i);}return false;}
}

---

1679. K 和数对的最大数目

题目

思路

哈希表计数

使用哈希表来存储数组中每个数字出现的次数，然后遍历数组寻找数对。

解题过程

1. 初始化一个计数器 ret = 0 和一个哈希表 map 来存储数字及其出现的频率。
2. 遍历数组 nums 中的每个元素 x：
   a. 计算需要配对的另一个数字 target = k - x。
   b. 检查哈希表 map 中是否存在 target，并且其计数大于0。
   c. 如果存在这样的 target：
   i. 说明找到了一个数对，操作数 ret 加 1。
   ii. 减少 target 在 map 中的计数。如果计数变为0，可以从 map 中移除 target。
   d. 如果不存在这样的 target（或者 target 的计数为0）：
   i. 将当前元素 x 加入到哈希表 map 中，或者将其在 map 中的计数加 1。
3. 遍历结束后，ret 即为最大操作数。

复杂度

• 时间复杂度: $O(N)$, 其中 N 是数组 nums 的长度。我们只需要遍历数组一次。哈希表的插入、查找和更新操作平均时间复杂度为 $O(1)$。
• 空间复杂度: $O(N)$, 最坏情况下，所有元素都不同且无法配对，哈希表需要存储 N 个元素的计数。

Code

class Solution {public int maxOperations(int[] nums, int k) {int ret = 0;Map<Integer, Integer> map = new HashMap<>(nums.length); // 初始化容量，小优化for (int x : nums) {int target = k - x;if (map.containsKey(target) && map.get(target) > 0) {ret++;int count = map.get(target);if (count == 1) {map.remove(target); // 或者 map.put(target, 0)} else {map.put(target, count - 1);}} else {map.put(x, map.getOrDefault(x, 0) + 1);}}return ret;}
}

---

2260. 必须拿起的最小连续卡牌数

题目

思路

哈希表 (数组模拟) / 滑动窗口思想

题目要求找到一对匹配的卡牌，使得拿起它们及它们之间的所有卡牌所需的卡牌数最少。这等价于找到两个相同卡牌的最小索引差。我们可以使用哈希表来记录每张卡牌最近出现的位置。

解题过程

1. 初始化一个变量 minPickup 为一个较大的值（例如 cards.length + 1），表示目前找到的最小卡牌数。
2. 使用一个数组来存储卡牌点数及其最后出现的索引。其大小需要覆盖卡牌点数的最大可能值（题目中点数范围是 0 到 1,000,000）。数组 posMap 的索引代表卡牌点数，值代表该点数卡牌最后出现的数组下标 + 1 (加1是为了区分未出现过的0和出现在索引0的情况)。
3. 遍历卡牌数组 cards，对于每个卡牌 cards[i]（在索引 i 处）：
   a. 检查 posMap[cards[i]] 是否大于0（即 cards[i] 之前是否出现过）。
   b. 如果 cards[i] 之前出现过，其上一次出现的索引是 prevIndex = posMap[cards[i]] - 1。
   c. 那么，拿起这两张相同卡牌以及它们之间的卡牌所需的数量是 i - prevIndex + 1。
   d. 更新 minPickup = Math.min(minPickup, i - prevIndex + 1)。
   e. 更新 posMap[cards[i]] = i + 1，记录当前卡牌 cards[i] 新的最后出现位置。
4. 遍历结束后，如果 minPickup 仍然是初始的大值，说明没有找到任何匹配的卡牌对，返回 -1。否则，返回 minPickup。

复杂度

• 时间复杂度: $O(N)$, 其中 N 是卡牌数组 cards 的长度。我们只需要遍历数组一次。
• 空间复杂度: $O(M)$, 其中 M 是卡牌点数的最大值（1,000,001），因为我们使用了一个固定大小的数组作为哈希映射。如果使用标准哈希表，则是 $O(U)$，U 为数组中不同卡牌点数的数量。

Code

class Solution {public int minimumCardPickup(int[] cards) {int minPickup = cards.length + 1;int[] lastPos = new int[1000001]; for (int i = 0; i < cards.length; i++) {int cardValue = cards[i];if (lastPos[cardValue] > 0) { minPickup = Math.min(minPickup, i - (lastPos[cardValue] - 1) + 1);}// 更新这张卡牌最后出现的位置为当前 (索引 + 1)lastPos[cardValue] = i + 1; }return minPickup == cards.length + 1 ? -1 : minPickup;}
}

---

624. 数组列表中的最大距离

题目

思路

贪心

要找到两个不同数组中元素的最大差值，我们只需要在遍历过程中维护到目前为止所有已遍历数组中的全局最小值和全局最大值。

解题过程

1. 初始化结果 maxDist = 0。

2. 初始化 prevMinVal 为第一个数组的最小值，prevMaxVal 为第一个数组的最大值。

3. 从列表中的第一个数组开始遍历 (或者，如果用第一个数组初始化 prevMinVal 和 prevMaxVal，则从第二个数组开始遍历)。对于当前遍历到的数组 currentArr：
   a. 获取 currentArr 的最小值 currentMin (即 currentArr.get(0)，因为数组已排序)。
   b. 获取 currentArr 的最大值 currentMax (即 currentArr.get(currentArr.size() - 1)).
   c. 最大距离的候选值有两个：
   i. currentMax - prevMinVal (当前数组的最大值与之前所有数组的最小值之差)
   ii. prevMaxVal - currentMin (之前所有数组的最大值与当前数组的最小值之差)
   d. 更新 maxDist = Math.max(maxDist, Math.max(currentMax - prevMinVal, prevMaxVal - currentMin)).
   e. 更新全局的 prevMinVal = Math.min(prevMinVal, currentMin)。
   f. 更新全局的 prevMaxVal = Math.max(prevMaxVal, currentMax)。

4. 遍历结束后，maxDist 即为所求的最大距离。

复杂度

• 时间复杂度: $O(N)$, 其中 N 是 arrays 列表中的数组数量。对于每个数组，我们只访问其第一个和最后一个元素，这通常是 $O(1)$ 操作。
• 空间复杂度: $O(1)$, 我们只需要常数级别的额外空间来存储 prevMin, prevMax, 和 ret。

Code

class Solution {public int maxDistance(List<List<Integer>> arrays) {int ret = 0;int prevMin = arrays.get(0).get(0);int prevMax = arrays.get(0).get(arrays.get(0).size() - 1);for (int i = 1; i < arrays.size(); i++) {List<Integer> currentArr = arrays.get(i);int currentMin = currentArr.get(0);int currentMax = currentArr.get(currentArr.size() - 1);ret = Math.max(ret, Math.abs(currentMax - prevMin));ret = Math.max(ret, Math.abs(prevMax - currentMin));prevMin = Math.min(prevMin, currentMin);prevMax = Math.max(prevMax, currentMax);}return ret;}
}

---