💖 ❄️我们的算法之路❄️💖
众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在算法学习的过程中我们总是能感受到算法的✨魅力✨。
☀️🌟短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼🌟☀️
💝二分，💝贪心，💝并查集，💝二叉树，💝图论，💝深度优先搜索(dfs) ，💝宽度优先搜索（bfs） ，💝数论，💝动态规划等等， 路漫漫其修远兮，吾将上下而求索！ 希望在此集训中与大家共同进步，有所收获！！！🎉🎉🎉
今日主题：前缀和
- 前缀和一般不会单独考察，更多的是基于二分，贪心，搜索等实际应用场景中进行优化所用，并且前缀合本身是极其简单的，难的是与其他算法的综合解决能力，所以小伙伴们针对前缀和也不能再持有单一的认识，在平时刷题时需要有意识地注意前缀和的综合问题。
👉⭐️第一题💎
✨题目
✨思路：
计算数组中的任意子数组的元素和,首先通过NumArray初始化数组时建立好一个前缀和数组，随后查询时直接在该sum数组中拿取边界数据即可，查询的时间复杂度基本为O(1)
✨代码：
class NumArray { public: vector<int>N; vector<int>sum; NumArray(vector<int>& nums) { N = nums; int n = nums.size(); sum.resize(n); sum[0] = nums[0]; for (int i = 1; i < n; i++) { sum[i] = sum[i - 1] + nums[i]; } } int sumRange(int left, int right) { return sum[right] - sum[left] + N[left]; } };
👉⭐️第二题💎
✨题目
对于每一种奇数长度Ni的情况，依次求出所有Ni长度的子数组（从数组首元素开始遍历Ni个数）的和并累加起来，其实也就是for循环的合理使用，这样的话就比较暴力，不过看着数据规模也不大，暴力当然也是能过的，不然就不会是简单题了，不管如何，先AC再说
✨代码：
class Solution { public: int add(vector<int>&arr,int i,int j){ int s=0; for(int t=i;t<j;t++){ s+=arr[t]; } return s; } int sumOddLengthSubarrays(vector<int>& arr) { int S=0; int n = arr.size(); for (int i = 1; i <= n; i += 2) { int dd = n - i; for (int j = 0; j <= dd; j += 1) { S+=add(arr,j,i+j); } } return S; } };
👉⭐️第三题💎
✨题目
✨思路：
哈希表与前缀和结合使用：哈希表存储前缀和，遇到符合题目要求的情况便累加吗，还可以利用滑动窗口求解，但是需要注意边界数据，比如[0,0,0,0] 0，这样就需要控制左滑窗的移动范围。
✨代码：
class Solution { public: int numSubarraysWithSum(vector<int>& nums, int goal) { map<int,int>record; record[0]++; int sum=0,num=0; for(auto i:nums){ num+=i; if(record[num-goal]) sum+=record[num-goal]; record[num]++; } return sum; } };
👉⭐️第四题💎
✨题目
有一把铲子卖k元，商店里有无数把这种铲子，你有无数个10元的硬币，但面值为r的硬币你只有1个(1<=r<=9)，请问你最少要买多少把铲子，商家才不需要给你找零
这道题我其实没有太明白，参考了题解才勉强写出，以后还需要增加英文阅读水平和提高代码能力哇
✨代码：
#include "bits/stdc++.h" using namespace std; #define ll long long #define forn(i,n) for(int i=0;i<n;i++) #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(),v.rend() #define pb push_back #define sz(a) (int)a.size() ll query(int l, int r, vector<ll>& p) { return p[r] - (l ? p[l - 1] : 0); } void solve() { int n, s; cin >> n >> s; vector<ll> a(n), p(n); forn(i, n) { cin >> a[i]; p[i] = a[i]; if(i) p[i] += p[i - 1]; } int ans = INT_MAX; for(int i = 0; i < n; ++i) { int l = i, r = n - 1, pos = -1; while(l <= r) { int mid = l + r >> 1; if(query(i, mid, p) <= s) { pos = mid; l = mid + 1; } else r = mid - 1; } if(pos == -1 || query(i, pos, p) != s) continue; ans = min(ans, n - (pos - i + 1)); } cout << (ans == INT_MAX ? -1 : ans) << "\n"; } int32_t main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t = 1; cin >> t; while(t--) { solve(); } }
写在最后：
相信大家对今天的集训内容的理解与以往已经有很大不同了吧，或许也感受到了算法的魅力,当然这是一定的，路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！
