每日算法刷题Day41 6.28:leetcode前缀和2道题，用时1h20min(要加快)

5. 523.连续的子数组和(中等,学习)

523. 连续的子数组和 - 力扣（LeetCode）

思想

1.给你一个整数数组 nums 和一个整数 k ，如果 nums 有一个 好的子数组 返回 true ，否则返回 false：
一个 好的子数组 是：

• 长度 至少为 2 ，且
• 子数组元素总和为 k 的倍数。
  注意：
• 子数组 是数组中 连续 的部分。
• 如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。0 始终 视为 k 的一个倍数。
  2.此题条件为(s[r+1]-s[l])%k=0且r-l+1>=2,变成s[r+1]%k=s[l]%k且(r+1)-l+1>=3,所以枚举j时，要看[0,j-3+1]是否有满足条件的(跟[0,j-1]不一样，不能边枚举边维护次数)，这时候就map的值最好为上一次出现的下标(通法)

代码

c++:

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        if (n < 2)
            return false;
        map<int, int> mp; // 和-下标
        mp[0] = -1;
        int s = 0;
        for (int j = 0; j < n; ++j) {
            s = (s + nums[j]) % k; // 都为正整数，无需变为负数
            if (mp.count(s)) {
                if (j - mp[s] + 1 >=
                    3) // 子数组长度大于等于2，前缀和数组下标差大于等于3
                    return true;
            } else
                mp[s] = j;
        }
        return false;
    }
};

6. 面试题17.05.字母与数字(中等,重点学习)

面试题 17.05. 字母与数字 - 力扣（LeetCode）

思想

1.给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。
返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。

代码

c++:

class Solution {
public:
    vector<string> findLongestSubarray(vector<string>& array) {
        int n = array.size();
        vector<int> s(n + 1);
        s[0] = 0;
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i];
            if (array[i][0] >= '0' && array[i][0] <= '9')
                ++s[i + 1];
            else
                --s[i + 1];
        }
        map<int, int> mp; // 次数-左下标
        int begin = 0, end = 0;
        for (int i = 0; i <= n; ++i) { // s数组范围:[0,n]
            auto it = mp.find(s[i]);
            if (it == mp.end()) {
                mp[s[i]] = i;
            } else if (i - it->second > end - begin) {
                end = i;
                begin = it->second;
            }
        }
        return {array.begin() + begin, array.begin() + end};
    }
};

一个变量s:

class Solution {
public:
    vector<string> findLongestSubarray(vector<string>& array) {
        int n = array.size(), begin = 0, end = 0, s = 0;
        unordered_map<int, int> mp;
        mp[s] = 0;                     // 初始前缀和为n时，位置为0
        for (int i = 1; i <= n; ++i) { // 从1开始遍历
            if (array[i - 1][0] >= '0' && array[i - 1][0] <= '9')
                ++s;
            else
                --s;
            auto it = mp.find(s);
            if (it == mp.end()) {
                // 如果没有出现过，记录该前缀和的第一次出现位置
                mp[s] = i;
            } else {
                // 如果出现过，计算当前子数组长度，更新最大子数组
                if (i - it->second > end - begin) {
                    begin = it->second;
                    end = i;
                }
            }
        }
        // 返回最大子数组
        return {array.begin() + begin, array.begin() + end};
    }
};