?歡迎光臨小站：致橡樹

和為K的子數組

給你一個整數數組 nums 和一個整數?k ，請你統計并返回 該數組中和為?k?的子數組的個數?。

子數組是數組中元素的連續非空序列。

示例 1：

輸入：nums = [1,1,1], k = 2
輸出：2

示例 2：

輸入：nums = [1,2,3], k = 3
輸出：2

提示：

• 1 <= nums.length <= 2 * 104

• -1000 <= nums[i] <= 1000

• -107 <= k <= 107

解題思路

雙循環枚舉（暴力法）

核心思想

枚舉所有可能的連續子數組，計算它們的和，統計和等于 K 的子數組數量

解題步驟

1. 外層循環遍歷起始位置

   for (int i = 0; i < nums.length; i++) {

   • 變量 i 表示子數組的起始位置

   • 從數組的第一個元素開始，逐步移動到最后一個元素

2. 內層循環遍歷結束位置

   for (int j = i; j < nums.length; j++) {

   • 變量 j 表示子數組的結束位置

   • 從起始位置 i 開始，逐步擴展到數組末尾

3. 計算子數組和

   sum += nums[j];

   • sum 變量累計從 i 到 j 的元素和

   • 每次內層循環添加一個新元素到當前子數組

4. 檢查和是否等于 K

   if (sum == k) {num++;
   }

   • 當子數組和等于目標值 K 時，計數器 num 增加 1

完整代碼

class Solution {public int subarraySum(int[] nums, int k) {int num = 0;for (int i = 0; i < nums.length; i++) {int sum = 0;for (int j = i; j < nums.length; j++) {sum += nums[j];if (sum == k) {num++;}}}return num;}
}

爬樓梯

假設你正在爬樓梯。需要 n?階你才能到達樓頂。

每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

示例 1：

輸入：n = 2
輸出：2
解釋：有兩種方法可以爬到樓頂。
1. 1 階 + 1 階
2. 2 階

示例 2：

輸入：n = 3
輸出：3
解釋：有三種方法可以爬到樓頂。
1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階

提示：

• 1 <= n <= 45

解題思路

這段代碼是解決"爬樓梯"問題的動態規劃實現。問題描述是：每次可以爬1或2個臺階，問爬到第n個臺階有多少種不同的方法。

規律發現

觀察 n=1 到 n=4 的結果：

• n=1 → 1 種（1）

• n=2 → 2 種（1+1 或 2）

• n=3 → 3 種（見上例）

• n=4 → 5 種（自己試試列舉）

發現了嗎？從第3階開始，方法數 = 前兩階方法數之和！
即：f(n) = f(n-1) + f(n-2)（比如 f(3)=f(2)+f(1)=2+1=3）

步驟分解

1. 初始化變量：

   • a = 1：表示到達第1個臺階有1種方法（1步）

   • b = 2：表示到達第2個臺階有2種方法（1+1步或直接2步）

   • c = a + b = 3：表示到達第3個臺階的方法數

2. 基本情況處理：

   • 如果n=1，直接返回1

   • 如果n=2，直接返回2

3. 循環計算：

   • 對于n≥3的情況，通過循環計算：

     • 每次迭代將變量向前移動：a取b的值，b取c的值，然后計算新的c=a+b

     • 這個循環會執行n-3次

     • 最終c的值就是到達第n個臺階的方法數

class Solution {public int climbStairs(int n) {int a = 1;int b = 2;int c = a + b;if (n == 1) {return a;}if (n == 2) {return b;}while (n - 3 > 0) {a = b;b = c;c = a + b;n--;}return c;}
}