2023-03-12发表2023-03-12更新学习6 分钟读完 (大约960个字)

力扣笔记

第一周

哈希表在连续数组中的应用

1.统计美丽子数组数目 6317

原题：

给你一个下标从 0 开始的整数数组nums 。每次操作中，你可以：

选择两个满足 0 <= i, j < nums.length 的不同下标 i 和 j 。
选择一个非负整数 k ，满足 nums[i] 和 nums[j] 在二进制下的第 k 位（下标编号从 0 开始）是 1 。
将 nums[i] 和 nums[j] 都减去 2k 。

如果一个子数组内执行上述操作若干次后，该子数组可以变成一个全为 0 的数组，那么我们称它是一个美丽的子数组。

请你返回数组 nums 中 美丽子数组 的数目。

子数组是一个数组中一段连续非空的元素序列。

// 朴素思想 TLE
class Solution {
public:
    static const int N = 25;
    static const int M = 1e5 + 10;
    int s[M][N] = {0};

    bool check(int l, int r)
    {
        for(int i = 1; i <= 21; i ++)
        {
            int t = s[r][i] - s[l - 1][i];
            if(t % 2) return false;
        }
        return true;
    }
    long long beautifulSubarrays(vector<int>& nums) {
        int n = nums.size();

        for(int i = 0; i < n;i ++)
        {
            int num = nums[i];
            for(int j = 0; j <= 20; j ++)
            {
                int k = num >> j & 1;
                if(k) s[i + 1][j + 1] += 1;
            }
        }

        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= 21; j ++)
                s[i][j] += s[i - 1][j];

        long long res = 0;
        for(int i = 0;i < n ;i ++)
            for(int j = i; j < n; j ++ )
                if(check(i + 1, j + 1)) res ++;
        return res;
    }
};

//利用哈希表来寻找左侧出现过的值 * 降低时间复杂度
class Solution {
public:
    long long beautifulSubarrays(vector<int>& nums) {
        int n = nums.size();
        vector<int> s(n + 1);
        
        //异或和  通过异或来简化统计二进制下不同位1个数的奇偶性
        for(int i = 1; i <= n ; i ++)
        {
            s[i] = s[i - 1] ^ nums[i - 1];
        }
        unordered_map<int, int> h;

        long long res = 0;
        for(auto c: s)
        {
            cout << c <<endl;
            // 此处表示异或和下的间隔，先+=再++
            res += h[c]++;
        }
        return res;
    }
};

2.使数组和能被 P 整除 1590

原题：

给你一个正整数数组 nums，请你移除最短子数组（可以为空），使得剩余元素的和能被 p 整除。 不允许 将整个数组都移除。

请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。

子数组 定义为原数组中连续的一组元素。
$$
找到i,j满足：S[i + 1:j] % p=0\
有前缀和性质使得(S[j]-S[i])%p=SUM%p
$$

class Solution {
public:
    int minSubarray(vector<int>& nums, int p) {
        int n = nums.size();
        int k = 0;
        for(auto c : nums)
        {
            k = (k + c) % p;
            // cout << k <<endl;
        }
        if(!k) return 0;
        int ans = n;
        unordered_map<int, int> h;
        int y = 0;
        //坐标保持一致
        h[0] = -1;
        for(int i = 0; i < n;i ++)
        {
            h[y] = i;
            y = (y + nums[i]) % p;
            if(h.count((y - k + p) % p))
            {
                //注意idx坐标位置、举例说明
                int idx = h[(y - k + p) % p] - 1;
                if(ans == -1 || ans > i - idx) ans = i - idx;
            }
        }
        //表示如果全部删除才能满足结果 返回-1
        return ans == n ? -1 : ans;

    }
};

3.连续的子数组和 523

原题：

给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：

子数组大小 至少为 2 ，且
子数组元素总和为 k 的倍数。

如果存在，返回 true ；否则，返回 false 。

如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。0 始终视为 k 的一个倍数。 注意n可以为0

代码：

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int, int> h;
        int s = 0;
        //特殊判断
        if(n < 2) return false;
		//坐标偏移
        h[0] = -1;
        for(int i = 0; i < n;i ++)
        {
            // h[s] = i;
            s = (nums[i] + s) % k;
            if(h.count(s))
            {
                int idx = h[s];
                if(i - idx >= 2) return true;
            }
            else 
 //可能存在有0的情况使得连续出现的s相同于是h[s]的值异常更新，使得最终长度<2；于是此处特殊判断存在s就跳过更新哈希表  （本题只需要判断1-0不需要长度所以简便即可）
            {
                h[s] = i;
            }
        }
        return false;
    }
};