【数组篇】119. 杨辉三角 II

118. 杨辉三角。

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1：

输入: rowIndex = 3
输出: [1,3,3,1]

示例 2：

输入: rowIndex = 0
输出: [1]

示例 3：

输入: rowIndex = 1
输出: [1,1]

提示：

0 <= numRows <= 33

算法分析

解题思路

数学法：从头往后处理

class Solution {
    public List<Integer> getRow(int rowIndex) {
        if (rowIndex < 0) {
            return new ArrayList<>();
        }
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> one = new ArrayList<>();
        one.add(1);
        ans.add(one);
        for (int i = 1; i <= rowIndex; i++) {
           List<Integer> res = new ArrayList<>();
           res.add(1);
           List<Integer> temp = ans.get(i - 1);
           for (int j = 1; j < i; j++) {
               res.add(temp.get(j - 1) + temp.get(j));
           }
           res.add(1);
           ans.add(res);
        }
        return ans.get(rowIndex);
    }
}

复杂性分析

时间复杂度：O(numRows2)
空间复杂度：O(1)