和为k的子数组
中等
提示
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1：
**输入：**nums = [1,1,1], k = 2
**输出：**2
示例 2：
**输入：**nums = [1,2,3], k = 3
**输出：**2
思路: 前缀和 加哈希表
function subarraySum(nums, k) {
let count = 0, sum = 0;
// 哈希表，键为前缀和，值为出现次数
const map = new Map([[0, 1]]);
for (const num of nums) {
sum += num;
// 查询前缀和为 sum - k 的出现次数
if (map.has(sum - k)) {
count += map.get(sum - k);
}
// 将前缀和加入哈希表
map.set(sum, (map.get(sum) || 0) + 1);
}
return count;
}
爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
function climbStairs(n) {
if (n <= 2) {
return n;
}
let dp = new Array(n + 1).fill(0);
dp[1] = 1;
dp[2] = 2;
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
杨辉三角
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
示例 1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1
输出: [[1]]
var generate = function(numRows) {
if(numRows === 1){
return [[1]]
}
if(numRows === 2){
return [[1],[1,1]]
}
let triangle = [];
for (let i = 0; i < numRows; i++) {
triangle[i] = new Array(i + 1);
triangle[i][0] = 1; // 每行的第一列为1
triangle[i][i] = 1; // 每行的最后一列为1
for (let j = 1; j < i; j++) {
triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
}
}
return triangle;
};
