119.md

119. Pascal's Triangle II

Given an index k, return the kth row of the Pascal's triangle.
For example, given k = 3, Return [1,3,3,1].
Note: Could you optimize your algorithm to use only O(k) extra space?

给定索引k，返回杨辉三角的第k行。
例如，给定k = 3，返回[1,3,3,1]。
注意：你能优化你的算法至只使用O(k)的空间复杂度吗？

题目要求O(k)的空间复杂度，就不能像118一样用二维数组了。
从两个数开始，末位添1，然后从后向前相加。

[1, 1] -> [1, 1, 1] -> [1, 2, 1] ->
[1, 2, 1, 1] -> [1, 2, 3, 1] -> [1, 3, 3, 1] ->
[1, 3, 3, 1, 1] -> [1, 3, 3, 4, 1] -> [1, 3, 6, 4, 1] -> [1, 4, 6, 4, 1]

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function(rowIndex) {
  if (rowIndex === 0) return [1];

  var row = [1];

  for(i = 1; i <= rowIndex; i++) {
    row[i] = 1;
    for(j = i - 1; j > 0; j--) {
      row[j] = row[j] + row[j-1];
    }
  }

  return row;
};

34 / 34 test cases passed.
Status: Accepted
Runtime: 108 ms