algorithm - 贪婪策略的算法思想

所以我刚考完试，想问你们一个困扰我的问题我被要求在n个数字的升序数组中使用greedy strategy提出算法思想，其中A[i] + A[j] = T。T只是一个数字，用来看看这两个数字是否相加我们要把它保持在O(n)。我不知道该怎么做。
我建议的方法是，如果不是的话，采取A[i] + A[j] > T直到你找到一个大于t的答案。一旦你发现它大于t，你就会从A[0]变成A[j-1]，看看它是否符合任何情况不过，我不认为我的想法是好的有什么想法吗？

最佳答案

这个想法是，对于从列表末尾开始的一个[i]的每个大值，你将搜索J的较小值，使得如果存在这样的J，则[i] +a[j]＝t。如果数组是无序的，这将是一个O（n^2）循环嵌套。
贪婪的部分是你永远不需要用j的值“倒退”，因为A的值是上升的也就是说，当你降低I的值时，j的所有可能的正确值必须大于当前值。
代码中：

i = n - 1;
j = 0;
while (j <= i)
  if (A[i] + A[j] < T)
    j++;
  else if (A[i] + A[j] > T)
    i--;
  else {
    printf("A[%d] + A[%d] = %d\n", i, j, T);
    break;
  }

关于algorithm - 贪婪策略的算法思想，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25024814/