👉引言
| 铭记于心 ||唯一知道的，便是我一无所知||
我们的算法之路
众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在算法学习的过程中我们总是能感受到算法的✨魅力✨
☀️🌟短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼🌟☀️
💝 二分，💝 贪心，💝 并查集，💝 二叉树，💝 图论，💝 深度优先搜索(dfs)，💝 宽度优先搜索（bfs），💝 数论，💝 动态规划等等， 路漫漫其修远兮，吾将上下而求索！ 希望在此集训中与大家共同进步，有所收获！！！🎉🎉🎉
今日主题：二分
👉🌟 第一题🌟
💎题目
👉思路：
直接使用STl中的二分查找函数，这里是找到大于等于target的数并返回迭代器，所以还要判断找到的数是不是严格等于target的
👉代码：
class Solution { public: int search(vector<int>& nums, int target) { int i=lower_bound(nums.begin(), nums.end(), target)-nums.begin(); if (i == nums.size())return -1; return nums[i] == target ? i : -1; } };
👉🌟第二题💎
👉题目
同样使用STL中的二分查找函数，找到等于target的数的个数，然后找到初始下标，随后每项+1并放入ans中，表示目标下标
👉代码：
class Solution { public: vector<int> targetIndices(vector<int>& nums, int target) { vector<int>ans; sort(nums.begin(), nums.end()); int i = lower_bound(nums.begin(), nums.end(), target) - nums.begin(); int n = (upper_bound(nums.begin(), nums.end(), target) - nums.begin())-i ; if (n <= 0)return ans; ans.resize(n); for (int t = 0; t < n; t++) { ans[t] = i++; } return ans; } };
👉🌟第三题💎
👉题目
👉思路：
用一个map解决
👉代码：
class Solution { public: int findDuplicate(vector<int>& nums) { map<int, int>ans; for (int i = 0; i < nums.size(); i++) { ans[nums[i]]++; if (ans[nums[i]] != 1)return nums[i]; } return -1; } };
👉🌟第四题💎
👉题目
👉:翻译：
👉代码：
#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(); } } 在这里插入代码片
💎写在最后： 🌟相信大家对今天的集训内容的理解与以往已经有很大不同了吧，或许也感受到了算法的魅力,当然这是一定的，路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！!🌹🌹
