【六月算法集训 】第八天之前缀和

《算法集训传送门》   👉引言

	铭记于心
	🎉✨🎉我唯一知道的，便是我一无所知🎉✨🎉

---

💖 ❄️我们的算法之路❄️💖

   众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在算法学习的过程中我们总是能感受到算法的✨魅力✨。
               ☀️🌟短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼🌟☀️
   💝二分，💝贪心，💝并查集，💝二叉树，💝图论，💝深度优先搜索(dfs)，💝宽度优先搜索（bfs），💝数论，💝动态规划等等， 路漫漫其修远兮，吾将上下而求索！ 希望在此集训中与大家共同进步，有所收获！！！🎉🎉🎉

---

今日主题：前缀和

---

 👉⭐️第一题💎💎💎    ✨题目

      1838. 最高频元素的频数

   ✨思路：

先排序，随后遍历数组，将每个数作为高频数来寻找该种情况下，计算k次 *** 作后能够有多少个这种数，取最大的一个即可

   ✨代码：

class Solution {
public:
   int maxFrequency(vector<int>& nums, int k) {
	sort(nums.begin(), nums.end());
	int n = nums.size();
	long long S[100010];
	int i,j;
	int ans = 0;
	for (i = 1; i <= n; i++) {
		S[i] = S[i - 1] + nums[i - 1];
	}
	i = 0;
	for (j = 1; j <= n; ++j) {
		long long s = (S[j] - S[j - 1]) * (j - i) - (S[j] - S[i]);
		while (s>k)
		{
			i++;
			s = (S[j] - S[j - 1]) * (j - i) - (S[j] - S[i]);
		}
		ans = max(ans, j - i);
	}
	return ans;
}
};

 👉⭐️第二题💎💎💎    ✨题目

      1590. 使数组和能被 P 整除

得到数组的前缀和后，(i,j]区间数组的和就等于sum[j]-sum[i] , 然后找出最长的一个数组和（%p==0）即可

   ✨代码：

class Solution {
public:
	int minSubarray(vector<int>& nums, int p) {
		long long allSum = 0;
		for (auto& num : nums)
			allSum += num;
		if (allSum < p) return -1;

		int mod = 0;
		mod = allSum % p;
		if (mod == 0) return 0;
		unordered_map<int, int> dict; 
		dict[0] = -1;
		const int len = nums.size();
		int minLen = len;
		long long preSum = 0;
		for (int i = 0; i < len; i++)
		{
			preSum += nums[i];
			int curMod = preSum % p;
			int target = (curMod - mod + p) % p; 
			if (dict.count(target))
				minLen = min(minLen, i - dict[target]);
			dict[curMod] = i; 
		}
		return minLen == len ? -1 : minLen;
	}
};

 👉⭐️第三题💎💎💎    ✨题目

      1589. 所有排列中的最大和

   ✨思路：

想象一个容器，把每个区间统计进去，对于每个区间，开始点 就当做是放进去，结束时间点 就是拿出去，那么同一时间 容器里面的数量 就等于当前这个点的重叠个数

   ✨代码：

class Solution
{
public:
    int maxSumRangeQuery(vector<int> &a, vector<vector<int>> &b)
    {
        int n = a.size();
        int mp[n + 1];
        memset(mp, 0, sizeof(mp));
        for (auto b : b)
        {
            int l = b[0], r = b[1];
            mp[l]++, mp[r + 1]--;
        }
        for (int i = 1; i < n; ++i)
            mp[i] += mp[i - 1];
        sort(mp, mp + n);
        sort(a.begin(), a.end());
        int mod = 1e9 + 7;
        long long res = 0;
        for (int i = n-1; i >=0; --i)
       (res+=(long long)a[i]*mp[i])%=mod;
        return res;
    }
};

 👉⭐️第四题💎💎💎    ✨题目

      1712. 将数组分成三个子数组的方案数

   ✨思路：

前缀和+二分查找

   ✨代码(python)：

N = 10 ** 9 + 7
class Solution:
    def waysToSplit(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(1, n):
            nums[i] += nums[i - 1]

        ans = 0
        for i in range(n - 2):
            p = bisect_left(nums, 2 * nums[i], i + 1, n - 1)
            q = bisect_right(nums, (nums[i] + nums[-1] ) / 2 , p, n - 1)
            ans += q - p

        return ans % N

---

  ⭐️总结⭐️

今天的题目比较难，前缀和很少单独使用，更多的是跟二分查找，排序等结合解题

写在最后：
相信大家对今天的集训内容的理解与以往已经有很大不同了吧，或许也感受到了算法的魅力,当然这是一定的，路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！