题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
class Solution {
public:
int sumImbalanceNumbers(vector<int>& nums) {
int res=0;
int n=nums.size();
for(int i=0;i<n;i++){
set<int> st;
st.insert(nums[i]);
st.insert(-2e9);
st.insert(2e9);
int now=0;
for(int j=i+1;j<n;j++){
auto it=st.lower_bound(nums[j]);
int pre=*prev(it);
int suf=*it;
int s=*next(it);
if(*it!=2e9&&pre!=-2e9)
{
if(*it-pre>1) now--;
}
if(pre!=-2e9)
{
if(nums[j]-pre>1) now++;
}
if(suf!=2e9){
if(suf-nums[j]>1) now++;
}
res+=now;
st.insert(nums[j]);
}
}
return res;
}
};
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
next没必要
是的,一开始写多了没想清楚