面试题—三个数之和小于某个值的组合个数
本题是阿里蚂蚁金服面试题:
给定一个数组s,和一个数a,在数组s里面找到3个数使这3个数的和小于a,即s[i]+s[j]+s[k]<a,请你设计一个函数返回数组s里这样的组合有多少个?
int f(double s[], double a) {
int cnt = 0;
Arrays.sort(s);
int i = 0;
int j = s.length;
while (i < j - 1) {
int low = i;
int high = j;
while (low < high) {
int k = (low + high) / 2;
if (s[i] + s[j] + s[k] >= a) {
high = k - 1;
} else if (s[i] + s[j] + s[k] < a) {
// 下面区间都是满足的
cnt += k - low;
// 二分查找
low = k + 1;
}
}
// 扫描结束,根据情况移动上下限
if (s[i] + s[j] > a) {
j--;
} else {
i++;
}
}
return cnt;
}
原文作者:JeemyJohn
原文地址: https://blog.csdn.net/u013709270/article/details/104671747
本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
原文地址: https://blog.csdn.net/u013709270/article/details/104671747
本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
相关文章