Lintcode: product of subarray exclude itself

左右分别scan法。

public class Solution {
    public ArrayList<Long> productExcludeItself(ArrayList<Integer> A) {
        ArrayList<Long> res = new ArrayList<Long>();
        if (A == null || A.size() == 0) {
          return res;
        }
        if (A.size() == 1) {
            res.add(1L);
            return res;
        }
        Long[] left = new Long[A.size()];
        Long[] right = new Long[A.size()];
        long product = 1;
        for (int i = 0; i < A.size(); i++) {
          product*= A.get(i);
          left[i] = product;
        }
        product = 1;
        for (int i = A.size()-1; i >= 0; i--) {
          product *= A.get(i);
          right[i] = product;
        }
        for (int i = 0; i < A.size(); i++) {
          if (i == 0) {
            res.add(right[i+1]);
          } else if (i == A.size() - 1) {
            res.add(left[i-1]);
          } else {
            res.add(left[i-1] * right[i+1]);
          }
        }
        return res;
    }
}