每日算法-250604

每日算法 - 250604

---

523. 连续的子数组和

题目

思路

前缀和 + 哈希表

解题过程

题目的目标是找到一个长度至少为 2 的连续子数组，其和是 k 的整数倍。

1. 核心思想：如果子数组 nums[j...i] 的和是 k 的倍数，那么 (sum(nums[j...i])) % k == 0。
   设 prefixSum[x] 为 nums[0...x] 的累积和。
   那么 sum(nums[j...i]) = prefixSum[i] - prefixSum[j-1] (当 j > 0)。
   如果 j = 0，则 sum(nums[0...i]) = prefixSum[i]。

2. 同余定理的应用：
   若 (prefixSum[i] - prefixSum[j-1]) % k == 0，
   则根据同余定理，prefixSum[i] % k == prefixSum[j-1] % k。

3. 哈希表优化：
   我们可以使用一个哈希表 map 来存储 (前缀和 % k) 的值及其首次出现的索引。

   • key: remainder = prefixSum % k
   • value: index

4. 遍历与判断：
   遍历数组 nums，计算到当前元素 nums[i] 为止的前缀和 currentPrefixSum。
   令 remainder = (int)(currentPrefixSum % k)。

   • 检查 map：
     如果 map 中已存在键 remainder，假设其对应的值（索引）为 prevIndex。
     这表示在 prevIndex 处的前缀和模 k 的余数，与当前在 i 处的前缀和模 k 的余数相同。
     因此，子数组 nums[prevIndex+1 ... i] 的和是 k 的倍数。
     该子数组的长度为 i - (prevIndex + 1) + 1 = i - prevIndex。
     我们需要确保此长度至少为 2，即 i - prevIndex >= 2。如果满足，则返回 true。
   • 存入 map：
     如果 map 中不存在键 remainder，则将 (remainder, i) 存入 map。我们只记录该 remainder 首次出现的索引，这是为了确保在找到匹配时，子数组 nums[prevIndex+1 ... i] 的长度 i - prevIndex 尽可能大，从而更容易满足长度 >= 2 的条件。

5. 初始化：
   为了处理子数组从索引 0 开始的情况 (即 prefixSum[j-1] 对应一个空的前缀和，其值为 0)，我们预先在 map 中放入 map.put(0, -1)。
   这样，如果到索引 i 的 currentPrefixSum % k == 0，我们就能找到 map 中的 (0, -1)。

复杂度

• 时间复杂度: $O(N)$，其中 $N$ 是数组 nums 的长度，因为我们只遍历数组一次。
• 空间复杂度: $O(\min (N,K))$，哈希表中最多存储 $\min (N,K)$ 个不同的余数及其索引。

Code

class Solution {public boolean checkSubarraySum(int[] nums, int k) {long prefix = 0;Map<Integer, Integer> map = new HashMap<>(nums.length + 1);map.put(0, -1);for (int i = 0; i < nums.length; i++) {prefix += nums[i];int key = (int) (prefix % k);if (map.containsKey(key)) {int preIndex = map.get(key);if (i - preIndex >= 2) {return true;}} else {map.put(key, i);}}return false;}
}

---

870. 优势洗牌（复习）

题目

解题思路回顾

这道题是“田忌赛马”策略的一个应用。这次写的还不错，就不再多说了，详细题解可以参考之前的博文：每日算法-250430

代码

class Solution {public int[] advantageCount(int[] nums1, int[] nums2) {int n = nums2.length;Integer[] indexs = new Integer[n];for (int i = 0; i < n; i++) {indexs[i] = i;}Arrays.sort(nums1);Arrays.sort(indexs, (a, b) -> (nums2[a] - nums2[b]));int[] ret = new int[n];for (int i = 0, left = 0, right = n - 1; i < n; i++) {int num1 = nums1[i], num2 = nums2[indexs[left]];if (num1 > num2) {ret[indexs[left]] = num1;left++;} else {ret[indexs[right]] = num1;right--;}}return ret;}
}