原题

  有n堆苹果，每堆苹果数量为a[i]个，给定m个数，每个数字为q[i]，从左往右数，求第q[i]个苹果在第几堆苹果里面。输入：n表示有n堆苹果，然后依次输入每堆苹果的个数a[i]，接着输入m表示一共需要计算m个苹果的位置，最后输入每个苹果的编号q[i]。输出：依次输出每个苹果的位置。样例如下：

输入:

  5
  2 7 3 4 9
  3
  1 25 11

输出:

  1
  5
  3

AC代码（Java）

import java.util.Scanner;

public class Main {
  public static int getBinarySearch(int[] arr, int k) {
    if (arr == null) {
      return -1;
    } else {
      int res = -1;
      int left = 0;
      int right = arr.length - 1;
      while (left <= right) {
        int middle = (left + right) / 2;
        if (k > arr[middle]) {
          left = middle + 1;
          res = middle + 1;
        } else if (k < arr[middle]) {
          right = middle - 1;
          res = middle;
        } else {
          res = middle;
          break;
        }
      }
      return res + 1;
    }
  }

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int[] ai = new int[n];
    for (int i = 0; i < ai.length; i++) {
      ai[i] = scanner.nextInt();
    }
    int m = scanner.nextInt();
    int[] qi = new int[m];
    for (int i = 0; i < qi.length; i++) {
      qi[i] = scanner.nextInt();
    }
    int[] sumArr = new int[n];
    sumArr[0] = ai[0];
    for (int i = 1; i < n; i++) {
      sumArr[i] = sumArr[i - 1] + ai[i];
    }
    int[] ansArr = new int[m];
    for (int i = 0; i < qi.length; i++) {
      ansArr[i] = getBinarySearch(sumArr, qi[i]);
    }
    for (int i = 0; i < ansArr.length; i++) {
      System.out.println(ansArr[i]);
    }
  }
}

思考

  此题要想得出正确的输出其实不难，暴力解也能输出。但在实际考试过程中提交代码时，暴力解法通过率仅为30%。暴力解法的思路无非是双循环，然后依次的去判断每个qi在ai中的位置，此时时间复杂度则为O（mn）。
  现在的互联网公司在笔、面试题中对于算法题目的考察，其实很多题目就是考对问题处理的时间复杂度，没完全通过的原因一般都是因为时间复杂度太大导致的，所以在笔试过程中如果说没完全通过，可以考虑优化时间复杂度。比如说复杂点的题目是否可以做成动态规划，简单点的题目是否用对了时间复杂度更低的方法。找准了思路，问题解决的目的性就可以变得很明确，可以快速的找到对应的方法去解决。比如经典的topK问题，一种解决思路就是去找一个时间复杂度尽可能低的算法去对k个数据进行排序比较，在这种场景下，自然就想到了堆排，大/小顶堆去实现。
  此题其实也不例外，当你用暴力法去解的时候。首先要思考的问题就是怎么去和数组的前几个数去比较，以确定q[i]的位置。此时其实有两种思路，一种是把a[j]前几个依次加起来，直到找到q[i]小于等于a[j]的前j个数组和的位置即为答案。另一种就是减法的思想，当q[i]大于a[j]时候，那么q[i]-a[j]，j++，直到找到q[i]<=a[j]，此时的位置即为答案。对于第一种思路，其实可以有优化的空间，因为你在每次比较q[i]的时候，其实都计算了a[j]的前j个数的和，这样就造成了计算重复，我们可以定义一个数组sumArr去储存前a[j]中前j数的和，这样我们就不必每次都去计算这个数值了。
  当我们定义完这个数组时，我们发现这个数组是一个有序递增数组。问题其实就转化成在一个有序数组中去查找目标数所在的区间，两个方法。
  1. 遍历数组，时间复杂度为O（n）
  2. 二分查找，时间复杂度为O（logn）
  很明显，果断选择二分查找，此时题目的时间复杂度则将为O（mlogn）。这样就可以顺利AC。