[美团0813笔试] 第四题三元组
[美团0813笔试] 第四题三元组
求一个数组的三元组个数，
因为：a[i] - a[j] = 2*a[i] - a[k]，
所以可以写成：a[i] + a[k] = 3*a[j]
所以可以写成：a[i] + a[k] = 3*a[j]
那么可以定义一个递归函数searchInRange(int startIndex, int endIndex)，每次在范围[i,k]内搜索满足上述公式的j，并逐渐缩小搜索范围
//
// Created by Harold on 2022/8/13/0013.
//
#include <iostream>
#include <vector>
using namespace std;
class Solution{
private:
int n_nums;
int res = 0;
vector<int> numList;
public:
void getInput(){
cin>>n_nums;
vector<int> numInput(n_nums);
for(int i = 0; i < n_nums; i++){
cin>>numInput[i];
}
numList = numInput;
}
void run(){
getInput();
getTheAns();
}
void searchInRange(int startIndex, int endIndex){
if(startIndex >= endIndex){
return;
}
int sum_ik = numList[startIndex] + numList[endIndex];
for(int i = startIndex+1; i < endIndex; i++){
if(3 * numList[i] == sum_ik){
res++;
}
}
searchInRange(startIndex+1, endIndex);
searchInRange(startIndex,endIndex-1);
}
void getTheAns(){
searchInRange(0,numList.size()-1);
cout<<res;
}
};
int main(){
Solution s;
s.run();
}