如何在最高效的 运行 时间内查找排序数组中连续元素的算术平均值是否等于给定值？
How to find if there's arithmatic mean of contiguous elements in a sorted array that equals to a given value in the most efficient running time?
输入：
- 已排序的正数自然数数组，
预期复杂度：
- 时间：
O(n)
- 其他 space：
O(1)
示例：
输入：
arr = {2,3,17,30}
x=10
预期行为：
该函数打印索引：1,2 和 returns 为真，因为 (3+17)/2 = x = 10
输入：
x = 30
预期行为：
该函数将打印索引 3
return 为真，因为 (30)/1 = x = 30`
我的算法方法：
我们将从数组中的第一个元素开始取算术平均值。如果 x 大于我们的结果，我们会将数组中的下一个元素添加到算术 mean.Else 我们将从算术平均值中减去第一个元素。
我试过了，没用。谁能帮帮我？
- 找到最大的 k，其中 a0+a1+a2+...+ak <= k*target
- 如果 sum == k*target - 好的
- 如果 sum != k*target - 添加下一个元素，然后减去第一个元素，直到平均值变得小于或等于目标。
如果你的k达到数组长度，无解。否则你有解决方案。复杂度 O(n) 就好像第 3 步你只加一个数字，因为前一个总和 + ak+1 大于 k*target 并且你只能移动左边界 n 次。
1. proc(array, x):
2. sum = 0;
3. left = 0;
4. right = 0;
5. do:
6. sum += array[right];
7. right++;
8. while (sum+array[right] <= (right+1)*target && right<array.size);
9. if (sum == right*target):
10. for (i = left; i < right; i++):
11. print(array[i] + <sep>);
12. end_for
13. return;
14. end_if
15. while (left <= right):
16. if (right<array.size): sum += array[right++];
17. do:
18. sum-=array[left++]
19. while (sum > target*(right-left));
20. if (sum == target*(right-left)):
21. for (i = left; i < right; i++):
22. print(array[i] + <sep>);
23. end_for
24. return;
25. end_if
26. end_while
27.end_proc
对于所有数字为正的数组都能正常工作。负数需要进行小的修改，但在面试中他们经常询问所有数字都是正数的数组。如果没有合适的解决方案，可能需要一些额外的转义条件。
如果我们计算 k 个元素的平均值 from 0 to k，我们可以了解平均值 from 1 to k 或 from 0 to k + 1 的哪些信息？
平均值 1 to k 和 0 to k + 1 均等于或大于前 k 元素的平均值。
为什么？
从子集 from 0 to k 到子集 from 1 to k，意味着删除最少的元素，因此可能不会降低总平均值。
从子集 from 0 to k 到子集 from 0 to k + 1，意味着添加一个不小于其他元素的元素，因此它可能不会降低总平均值。
我们知道给定数组中的哪个数字必须是结果的一部分吗？是的，这是最后一个小于或等于的目标。为什么？
当它相等时，我们就完成了
当不相等的时候，我们就需要bigger和lower元素都存在。
然后，我们通过从右侧添加元素并从左侧减少元素来保持平均值增加。
public static int[] findMean(int[] input, int target) {
int firstGreater = 0;
int n = input.length;
while(firstGreater < n && input[firstGreater] <= target) firstGreater++; // use binary search instead!
if(firstGreater == 0 || firstGreater == n) return new int[]{-1,-1};
int left = firstGreater - 1, right = firstGreater;
long sum = input[left];
while ((right < n &&(right - left) * target > sum) || (left > 0 && (right - left) * target < sum)) {
if((right - left) * target > sum) sum += input[right++];
else sum += input[--left];
}
if((right - left) * target != sum) {
left = right = -1;
}
return new int[]{left, right - 1};
}
输入：
- 已排序的正数自然数数组，
预期复杂度：
- 时间：
O(n) - 其他 space：
O(1)
示例：
输入：
arr = {2,3,17,30}
x=10
预期行为：
该函数打印索引：1,2 和 returns 为真，因为 (3+17)/2 = x = 10
输入：
x = 30
预期行为：
该函数将打印索引 3
return 为真，因为 (30)/1 = x = 30`
我的算法方法：
我们将从数组中的第一个元素开始取算术平均值。如果 x 大于我们的结果，我们会将数组中的下一个元素添加到算术 mean.Else 我们将从算术平均值中减去第一个元素。
我试过了，没用。谁能帮帮我？
- 找到最大的 k，其中 a0+a1+a2+...+ak <= k*target
- 如果 sum == k*target - 好的
- 如果 sum != k*target - 添加下一个元素，然后减去第一个元素，直到平均值变得小于或等于目标。
如果你的k达到数组长度，无解。否则你有解决方案。复杂度 O(n) 就好像第 3 步你只加一个数字，因为前一个总和 + ak+1 大于 k*target 并且你只能移动左边界 n 次。
1. proc(array, x):
2. sum = 0;
3. left = 0;
4. right = 0;
5. do:
6. sum += array[right];
7. right++;
8. while (sum+array[right] <= (right+1)*target && right<array.size);
9. if (sum == right*target):
10. for (i = left; i < right; i++):
11. print(array[i] + <sep>);
12. end_for
13. return;
14. end_if
15. while (left <= right):
16. if (right<array.size): sum += array[right++];
17. do:
18. sum-=array[left++]
19. while (sum > target*(right-left));
20. if (sum == target*(right-left)):
21. for (i = left; i < right; i++):
22. print(array[i] + <sep>);
23. end_for
24. return;
25. end_if
26. end_while
27.end_proc
对于所有数字为正的数组都能正常工作。负数需要进行小的修改，但在面试中他们经常询问所有数字都是正数的数组。如果没有合适的解决方案，可能需要一些额外的转义条件。
如果我们计算 k 个元素的平均值 from 0 to k，我们可以了解平均值 from 1 to k 或 from 0 to k + 1 的哪些信息？
平均值 1 to k 和 0 to k + 1 均等于或大于前 k 元素的平均值。
为什么？
从子集 from 0 to k 到子集 from 1 to k，意味着删除最少的元素，因此可能不会降低总平均值。
从子集 from 0 to k 到子集 from 0 to k + 1，意味着添加一个不小于其他元素的元素，因此它可能不会降低总平均值。
我们知道给定数组中的哪个数字必须是结果的一部分吗？是的，这是最后一个小于或等于的目标。为什么？ 当它相等时，我们就完成了 当不相等的时候，我们就需要bigger和lower元素都存在。
然后，我们通过从右侧添加元素并从左侧减少元素来保持平均值增加。
public static int[] findMean(int[] input, int target) {
int firstGreater = 0;
int n = input.length;
while(firstGreater < n && input[firstGreater] <= target) firstGreater++; // use binary search instead!
if(firstGreater == 0 || firstGreater == n) return new int[]{-1,-1};
int left = firstGreater - 1, right = firstGreater;
long sum = input[left];
while ((right < n &&(right - left) * target > sum) || (left > 0 && (right - left) * target < sum)) {
if((right - left) * target > sum) sum += input[right++];
else sum += input[--left];
}
if((right - left) * target != sum) {
left = right = -1;
}
return new int[]{left, right - 1};
}