刷题记录帖子

1581. Customer Who Visited but Did Not Make Any Transactions

1. import pandas as pd
   
2. 
   
3. def find_customers(visits: pd.DataFrame, transactions: pd.DataFrame) -> pd.DataFrame:
   
4.     vistit_no_transactions = visits[~visits.visit_id.isin(transactions.visit_id)]
   
5.     df = vistit_no_transactions.groupby('customer_id', as_index=False)['visit_id'].count()
   
6.     return df.rename(columns={'visit_id': 'count_no_trans'})

复制代码

1152. Analyze User Website Visit Pattern

You are given two string arrays username and website and an integer array timestamp. All the given arrays are of the same length and the tuple [username[i], website[i], timestamp[i]] indicates that the user username[i] visited the website website[i] at time timestamp[i].

A pattern is a list of three websites (not necessarily distinct).

For example, ["home", "away", "love"], ["leetcode", "love", "leetcode"], and ["luffy", "luffy", "luffy"] are all patterns.
The score of a pattern is the number of users that visited all the websites in the pattern in the same order they appeared in the pattern.

For example, if the pattern is ["home", "away", "love"], the score is the number of users x such that x visited "home" then visited "away" and visited "love" after that.
Similarly, if the pattern is ["leetcode", "love", "leetcode"], the score is the number of users x such that x visited "leetcode" then visited "love" and visited "leetcode" one more time after that.
Also, if the pattern is ["luffy", "luffy", "luffy"], the score is the number of users x such that x visited "luffy" three different times at different timestamps.
Return the pattern with the largest score. If there is more than one pattern with the same largest score, return the lexicographically smallest such pattern.

Note that the websites in a pattern do not need to be visited contiguously, they only need to be visited in the order they appeared in the pattern.



Example 1:

Input: username = ["joe","joe","joe","james","james","james","james","mary","mary","mary"], timestamp = [1,2,3,4,5,6,7,8,9,10], website = ["home","about","career","home","cart","maps","home","home","about","career"]
Output: ["home","about","career"]
Explanation: The tuples in this example are:
["joe","home",1],["joe","about",2],["joe","career",3],["james","home",4],["james","cart",5],["james","maps",6],["james","home",7],["mary","home",8],["mary","about",9], and ["mary","career",10].
The pattern ("home", "about", "career") has score 2 (joe and mary).
The pattern ("home", "cart", "maps") has score 1 (james).
The pattern ("home", "cart", "home") has score 1 (james).
The pattern ("home", "maps", "home") has score 1 (james).
The pattern ("cart", "maps", "home") has score 1 (james).
The pattern ("home", "home", "home") has score 0 (no user visited home 3 times).
Example 2:

Input: username = ["ua","ua","ua","ub","ub","ub"], timestamp = [1,2,3,4,5,6], website = ["a","b","a","a","b","c"]
Output: ["a","b","a"]


Constraints:

3 <= username.length <= 50
1 <= username[i].length <= 10
timestamp.length == username.length
1 <= timestamp[i] <= 109
website.length == username.length
1 <= website[i].length <= 10
username[i] and website[i] consist of lowercase English letters.
It is guaranteed that there is at least one user who visited at least three websites.
All the tuples [username[i], timestamp[i], website[i]] are unique.

1. class Solution:
   
2.     def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:
   
3.         data = [(user, ts, site) for user, ts, site in zip(username, timestamp, website)]
   
4.         data = sorted(data, key = lambda x: x[1])
   
5. 
   
6.         user_path = collections.defaultdict(list)
   
7.         for d in data:
   
8.             user_path[d[0]].append(d[2])
   
9. 
   
10.         freq_count = collections.defaultdict(int)
    
11.         for u, u_path in user_path.items():
    
12.             distinct_path = set()
    
13.             for i in range(len(u_path)):
    
14.                 for j in range(i+1, len(u_path)):
    
15.                     for k in range(j+1, len(u_path)):
    
16.                         distinct_path.add((u_path[i], u_path[j], u_path[k]))
    
17.             for k in distinct_path:
    
18.                 freq_count[k] += 1
    
19. 
    
20.         maxCount = -1
    
21.         res  = ()
    
22.         for k, v in freq_count.items():
    
23.             if v > maxCount or (v == maxCount and k < res):
    
24.                 maxCount = v
    
25.                 res = k
    
26.         
    
27.         return list(res)
    
28. 
    
29.    
    
30. 
    
31. 
    
32.         

复制代码

1. class Node:
   
2.     def __init__(self, name, timestamp, website):
   
3.         self.name = name
   
4.         self.timestamp = timestamp
   
5.         self.website = website
   
6. 
   
7. 
   
8. class Solution:
   
9.     def mostVisitedPattern(
   
10.         self, username: List[str], timestamp: List[int], website: List[str]
    
11.     ) -> List[str]:
    
12.         nodes = [
    
13.             Node(name, ts, site)
    
14.             for name, ts, site in zip(username, timestamp, website)
    
15.         ]
    
16.         nodes.sort(key=lambda x: x.timestamp)
    
17.         user_visits = defaultdict(list)
    
18.         for node in nodes:
    
19.             user_visits[node.name].append(node)
    
20. 
    
21.         route = defaultdict(int)
    
22.         for visits in user_visits.values():
    
23.             tmp = set()
    
24.             for i, j, k in combinations(range(len(visits)), 3):
    
25.                 path = (visits[i].website, visits[j].website, visits[k].website)
    
26.                 tmp.add(path)
    
27.             for path in tmp:
    
28.                 route[path] += 1
    
29. 
    
30.         max_count = -1
    
31.         result = ()
    
32.         for path, count in route.items():
    
33.             if count > max_count or (count == max_count and path < result):
    
34.                 max_count = count
    
35.                 result = path
    
36.         return list(result)

复制代码

1603. Design Parking System

1. class ParkingSystem:
   
2. 
   
3.     def __init__(self, big: int, medium: int, small: int):
   
4.         self.spaces = [big, medium, small]
   
5.         self.status = [0, 0, 0]
   
6.         
   
7. 
   
8.     def addCar(self, carType: int) -> bool:
   
9.         if self.status[carType-1] + 1 > self.spaces[carType-1]: return False
   
10.         else:
    
11.             self.status[carType-1] += 1
    
12.             return True
    
13. 
    
14. 
    
15. # Your ParkingSystem object will be instantiated and called as such:
    
16. # obj = ParkingSystem(big, medium, small)
    
17. # param_1 = obj.addCar(carType)

复制代码

1661. Average Time of Process per Machine

用负数来使得 start time 可以自动剪掉。

1. def get_average_time(activity: pd.DataFrame) -> pd.DataFrame:
   
2. 
   
3.     activity['timestamp'] = activity.apply(lambda x: x.timestamp * -1 if x.activity_type == 'start' else x.timestamp, axis=1)
   
4. 
   
5.     sum_machine_process = activity.groupby(['machine_id', 'process_id'], as_index=False)['timestamp'].sum()
   
6. 
   
7.     mean_machine = sum_machine_process.groupby(['machine_id'], as_index=False)['timestamp'].mean().round(3).rename(columns = {'timestamp': 'processing_time'})
   
8.    
   
9.     return mean_machine

复制代码

1757. Recyclable and Low Fat Products

1. import pandas as pd
   
2. 
   
3. def find_products(products: pd.DataFrame) -> pd.DataFrame:
   
4.     df = products[(products['low_fats'] == 'Y') & (products['recyclable'] == 'Y')]
   
5.     df = df[['product_id']]
   
6.     return df
   
7.    

复制代码

3314. Construct the Minimum Bitwise Array I
3315. Construct the Minimum Bitwise Array II

1. class Solution:
   
2.     def minBitwiseArray(self, nums: List[int]) -> List[int]:
   
3.         ans = []
   
4.         for i in range(len(nums)):
   
5.             res = -1
   
6.             d = 1 # mask
   
7.             while (nums[i] & d) != 0:
   
8.                 res = nums[i] - d
   
9.                 d <<= 1
   
10.             ans.append(res)
    
11.         return ans
    
12.         

复制代码

Only data length are different, so brute force works for I but not for II.

But the following log operations works

这段代码其实是一个经典 bit trick 的反向构造。我按「在干什么 → 为什么这样做 → 举例」来解释。

一、这段代码在干什么（整体）

对 nums 里的每个数 x：

找到一个 最小的 y，使得
y | (y + 1) == x
如果找不到，就返回 -1

最终返回的是一个数组，每个元素是对应的 y。

二、逐行解释
for i in range(len(nums)):


遍历数组里的每个数。

res = -1


默认结果是 -1，表示不存在合法解。

d = 1


d 是一个 bit mask，从最低位开始（1, 2, 4, 8, ...）。

while (nums[i] & d) != 0:


意思是：
👉 只要 nums[i] 在第 d 这一位上是 1，就继续

也就是说：

从最低位开始

一直扫 连续的 trailing 1s

res = nums[i] - d


关键行 🔑

如果 nums[i] 在 d 位是 1：

尝试把这一位 清零

得到候选值 y = nums[i] - d

d <<= 1


检查下一位（左移一位）。

nums[i] = res


循环结束后，把找到的 最后一个合法 y 写回数组。

三、为什么这能反推出 y | (y+1) = x？

回忆我们之前说的结论：

y | (y+1)
会把 y 的 trailing 1s 以及它左边的第一个 0 全变成 1

那么反过来想：

如果 x = y | (y+1)，那 x 必须：

最低位开始是连续的 1

一旦遇到 0，就结束（不能再往上）

所以：

能构造 y 的前提：
x 至少有一个 trailing 1

四、代码的核心逻辑（精华）

while (nums[i] & d) != 0
👉 扫描 x 的 trailing 1s

每遇到一个 1：

y = x - d


相当于：

把某一位从 1 变成 0

低位保持为 1

最后一次成功的 y：

对应的是：
👉 把 最左边的 trailing 1 变成 0

这是 最小的 y

五、举例说明
例 1：x = 7 (111)
d = 1 → 111 & 001 = 1 → res = 6 (110)
d = 2 → 111 & 010 = 2 → res = 5 (101)
d = 4 → 111 & 100 = 4 → res = 3 (011)
d = 8 → 111 & 1000 = 0 → stop


结果：

y = 3
3 | 4 = 7 ✅

例 2：x = 8 (1000)
8 & 1 = 0 → while 不进
res = -1


因为没有 trailing 1：

不存在 y 使得 y | (y+1) = 8

六、一句话总结（面试版）

这段代码对每个 x，从最低位开始扫描 trailing 1s，
尝试逐步清掉某一位 1，
找到最小的 y，使得 y | (y+1) == x，
若 x 没有 trailing 1，则返回 -1。

1. class Solution:
   
2.     def minBitwiseArray(self, nums: List[int]) -> List[int]:
   
3.         for i in range(len(nums)):
   
4.             res = -1
   
5.             d = 1
   
6.             while (nums[i] & d) != 0:
   
7.                 res = nums[i] - d
   
8.                 d <<= 1
   
9.             nums[i] = res
   
10.         return nums

复制代码

5. Longest Palindromic Substring

Brute Force, O(N^3)

1. class Solution:
   
2.     def longestPalindrome(self, s: str) -> str:
   
3.         def check(i, j):
   
4.             left = i      # start
   
5.             right = j - 1 # start + curr_substring_length
   
6.             while left < right:
   
7.                 if s[left] != s[right]: return False
   
8.                 left += 1
   
9.                 right -= 1
   
10.             return True
    
11. 
    
12.         for length in range(len(s), 0, -1):
    
13.             for start in range(len(s) - length + 1):
    
14.                 if check(start, start+length):
    
15.                     return s[start : start+length]

复制代码

DP solution

1. class Solution:
   
2.     def longestPalindrome(self, s: str) -> str:
   
3.         # dp
   
4.         # dp[i][j] = dp[i+1][j-1] AND (s[i] == s[j])
   
5. 
   
6.         n = len(s)
   
7.         dp = [[False] * n for _ in range(n)]
   
8.         ans = (0, 0)
   
9. 
   
10.         # fill digonal line
    
11.         for i in range(n):
    
12.             dp[i][i] = True
    
13.             ans = (i, i)
    
14.         
    
15.         # fill i, i+1 line
    
16.         for i in range(n-1):
    
17.             j = i + 1
    
18.             if s[i] == s[j]:
    
19.                 dp[i][j] = True
    
20.                 ans = (i, j)
    
21.         # fill for length >= 3 substrings
    
22.         for length in range(2, n, 1):
    
23.             for i in range(n - length):
    
24.                 j = i + length
    
25.                 if s[i] == s[j] and dp[i+1][j-1]:
    
26.                     dp[i][j] = True
    
27.                     ans = (i, j)
    
28.         return s[ans[0]:ans[1]+1] #+1 was due to String Slice

复制代码

128. Longest Consecutive Sequence


class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        freq = set(nums)

        maxLen = 0

        for num in freq:
            # ensures we only start counting from the beginning of a sequence.
            if num - 1 in freq: continue
            currLen = 1
            while num+1 in freq:
                num = num+1
                currLen += 1
            maxLen = max(currLen, maxLen)

        return maxLen

3752. Lexicographically Smallest Negated Permutation that Sums to Target

注意不要在遍历 list 的时候删除元素，可以直接原地改变。

1. class Solution:
   
2.     def lexSmallestNegatedPerm(self, n: int, target: int) -> List[int]:
   
3.         """
   
4.         once n set, the numbers will be used is fix, shall be abs(x), x from 1,2,3...n, either postive or negative
   
5. 
   
6.         so the maxSum will be (n+1) * n /2
   
7.         minSum = -1 * maxSum
   
8. 
   
9.         target must [minSum, maxSum]
   
10. 
    
11.         if target = maxSum or target = minSum, return all postive or all neagtive
    
12.         else:
    
13.             we start from all postive values and the flip the largest possible values to reach lexicographically smallest array
    
14.             you shall put larger values to negative ones to make it lexicographically smallest
    
15. 
    
16.             diff = maxSum - target
    
17.         
    
18.         k from n to 1,
    
19.             if 2*k > diff, continue
    
20.             if 2*k == diff
    
21.                 ans = [1,2.... - k,....n]
    
22.             else:
    
23.                 diff = diff - 2k
    
24.                 ans = [1,2.... - k,....n]
    
25.         """
    
26.         maxSum = n * (n+1) / 2
    
27.         if target > maxSum or target < -1 * maxSum: return []
    
28.         if target == maxSum: return [i for i in range(1, n+1)]
    
29.         if target == -1 * maxSum: return sorted([-1*i for i in range(1, n+1)])
    
30. 
    
31.         diff = maxSum -  target
    
32.         ans = []
    
33. 
    
34.         for k in range(n, 0, -1):
    
35.             if 2*k <= diff:
    
36.                 diff -= 2*k
    
37.                 ans.append(-1* k)
    
38.             else:
    
39.                 ans.append(k)
    
40. 
    
41.         if diff != 0: return []
    
42.         return sorted(ans)

复制代码

好，这题其实**想法很巧，但一旦抓住关键就很顺**。我按「**问题重述 → 关键观察 → 构造思路 → 为什么字典序最小 → 边界情况**」来讲。

---

## 一、题目在要求什么（换句话说）

你要构造一个长度为 `n` 的数组 `a`，满足：

1. **和等于 `target`**
2. **`|a[i]|` 恰好是 `{1,2,...,n}` 的一个排列**

   * 每个数 `1..n` 用一次
   * 但可以是正的，也可以是负的
3. 在所有合法解里，返回 **字典序最小** 的那个

如果做不到，返回 `[]`。

---

## 二、关键观察 1：总和能到的范围是有限的

如果所有数都取正：

```
maxSum = 1 + 2 + ... + n = n(n+1)/2
```

如果所有数都取负：

```
minSum = -maxSum
```

👉 **必要条件**：

```
-target ∈ [ -maxSum , maxSum ]
```

不在这个区间，**直接无解**。

> 这一步可以直接剪掉很多情况（Example 2）。

---

## 三、关键观察 2：从“全正”开始最容易控制

先假设数组是：

```
[1, 2, 3, ..., n]
```

此时：

```
sum = maxSum
```

如果 `sum == target`，直接返回。

否则我们需要 **降低总和**。

---

## 四、翻转一个数能改变多少和？

如果把 `k` 从 `+k` 变成 `-k`：

```
sum 减少 2k
```

👉 所以问题变成：

> 用若干个 `2k`，凑出
> `diff = maxSum - target`

---

## 五、关键观察 3：为什么要“优先翻转大的数”

我们要满足两个目标：

1. **和要对**
2. **字典序最小**

### 字典序最小 ≈ 前面的数尽量小

* 负数 < 正数
* 绝对值越大，负数越小（-n 最小）

👉 **想让字典序最小，就要让前面尽量出现大的负数**

所以策略是：

> **优先考虑把大的数变成负数**

---

## 六、核心贪心思路（非常重要）

令：

```
diff = maxSum - target
```

从 `k = n → 1`：

* 如果 `diff >= 2k`

  * 把 `k` 变成 `-k`
  * `diff -= 2k`
* 否则跳过

最后如果：

```
diff != 0
```

说明凑不出来 → 返回 `[]`

---

## 七、为什么这个贪心是对的？

### 1️⃣ 可行性

* `2, 4, 6, ..., 2n` 覆盖所有偶数
* `diff` 一定是偶数（`maxSum` 和 `target` 同奇偶）

👉 用 `2k` 是**完备的**

---

### 2️⃣ 字典序最小性（这是重点）

* 翻转大的数：

  * 会产生 **更小的负数**
  * 且这些负数在排序后会排在最前面
* 如果你先翻小的数：

  * 会让 `-1, -2` 提前
  * 但错过 `-n, -(n-1)` 这种更小的数

👉 **从大到小翻，字典序一定最小**

---

## 八、最后一步：排序！

注意：
我们构造的是一个集合，并不保证顺序。

但题目只关心 **数组本身的字典序**，
所以最后要：

```
排序数组（升序）
```

负的大数自然排最前面。

---

## 九、完整流程总结（面试版）

1. 计算 `maxSum = n(n+1)/2`
2. 如果 `target` 不在 `[-maxSum, maxSum]` → `[]`
3. `diff = maxSum - target`
4. 从 `k = n → 1`，如果 `diff >= 2k`，翻转 `k`
5. 如果 `diff != 0` → `[]`
6. 对结果排序，返回

---

## 十、Example 1 走一遍

```
n = 3
target = 0
maxSum = 6
diff = 6
```

从大到小：

* k = 3 → diff >= 6 → 翻 → diff = 0

结果集合：

```
[-3, 1, 2]
```

排序后：

```
[-3, 1, 2] ✅
```

---

## 十一、一句话记忆法

> 从 `[1..n]` 全正开始，
> 用“翻转大数”来抵消多余的和，
> 最后排序即可得到 **字典序最小解**。

---

560. Subarray Sum Equals K

1. class Solution:
   
2.     def subarraySum(self, nums: List[int], k: int) -> int:
   
3.         """
   
4.         preSum = [0] * (len(nums) + 1)
   
5. 
   
6.         for i in range(len(nums)): preSum[i+1] = preSum[i] + nums[i]
   
7.         
   
8.         ans = 0
   
9.         for i in range(0, len(nums)+1):
   
10.             for j in range(i+1, len(nums)+1):
    
11.                 if preSum[j] - preSum[i] == k: ans += 1
    
12.         return ans
    
13.         """
    
14.         currSum = 0
    
15.         preSum = collections.defaultdict(int)
    
16.         preSum[0] = 1
    
17.         ans = 0
    
18. 
    
19.         for num in nums:
    
20.             currSum += num
    
21.             if currSum - k in preSum:
    
22.                 ans += preSum[currSum - k]
    
23.             preSum[currSum] += 1
    
24. 
    
25.         return ans
    
26. 
    

复制代码

好，这一题是 **“Subarray Sum Equals K（和为 K 的子数组个数）”** 的经典解法。
我用 **直觉 → 数学关系 → 哈希表怎么用 → 走一遍例子** 来给你彻底讲清楚。

---

## 一、问题一句话版

给你一个数组 `nums` 和一个整数 `k`，
**问：有多少个连续子数组的和等于 `k`？**

---

## 二、核心直觉（这一步最重要）

### 定义前缀和

令：

```
sum[i] = nums[0] + nums[1] + ... + nums[i]
```

那么区间 `(j+1 ... i)` 的和是：

```
sum[i] - sum[j]
```

---

## 三、关键数学结论（题解里的那段话）

### 1️⃣ 为什么「前缀和相等 → 中间和为 0」

如果：

```
sum[i] == sum[j]
```

那么：

```
sum[i] - sum[j] = 0
```

👉 `j+1` 到 `i` 的子数组和为 **0**

---

### 2️⃣ 推广到一般情况（真正用到的）

如果：

```
sum[i] - sum[j] = k
```

等价于：

```
sum[j] = sum[i] - k
```

👉 **只要之前出现过 `sum[i] - k`，就说明存在一个子数组和为 `k`，并且以 `i` 结尾**

---

## 四、HashMap 在这里干什么？

我们用一个 hashmap（字典）：

```
map[前缀和] = 出现次数
```

它的作用是：

> 快速告诉我：
> **“到目前为止，有多少个前缀和等于某个值”**

---

## 五、算法流程（一步一步）

### 初始化

```python
count = 0
curr_sum = 0
map = {0: 1}
```

⚠️ `0:1` 很关键：

* 表示「在数组开始前，有一个前缀和为 0」
* 这样可以正确处理 **从下标 0 开始的子数组**

---

### 遍历数组

对每个 `num`：

1. 更新前缀和

   ```python
   curr_sum += num
   ```

2. 看有没有 `curr_sum - k`

   ```python
   if curr_sum - k in map:
       count += map[curr_sum - k]
   ```

3. 把当前前缀和加入 hashmap

   ```python
   map[curr_sum] += 1
   ```

---

## 六、为什么要「出现次数」，而不是 True / False？

因为：

> **同一个前缀和可能出现多次**

每出现一次：

* 都代表一个不同的起点
* 都能形成一个新的子数组

---

## 七、完整走一遍例子（非常关键）

### 示例

```python
nums = [1, 2, 3]
k = 3
```

---

### 初始状态

```
map = {0:1}
curr_sum = 0
count = 0
```

---

### i = 0, num = 1

```
curr_sum = 1
curr_sum - k = -2 → 不存在
map = {0:1, 1:1}
```

---

### i = 1, num = 2

```
curr_sum = 3
curr_sum - k = 0 → map[0] = 1
count += 1
```

子数组：

```
[1,2]
```

更新 map：

```
map = {0:1, 1:1, 3:1}
```

---

### i = 2, num = 3

```
curr_sum = 6
curr_sum - k = 3 → map[3] = 1
count += 1
```

子数组：

```
[3]
```

---

### 最终结果

```
count = 2
```

---

## 八、为什么这是 O(n)？

* 每个元素 **只遍历一次**
* hashmap 查询是 **O(1)**

相比暴力解法：

| 方法            | 时间复杂度    |
| ------------- | -------- |
| 三重循环          | O(n³)    |
| 前缀和 + 双循环     | O(n²)    |
| 前缀和 + HashMap | **O(n)** |

---

## 九、一句话总结（面试必背）

> 通过前缀和，把「子数组和为 k」转化为
> 查找是否存在 `sum[i] - k`，
> 使用 HashMap 记录前缀和出现次数，
> 从而在 O(n) 时间内完成统计。

---


这个问题问得**非常到位**，基本就是这道题的“分水岭理解点”。我直接给你一个**清晰对比 + 直觉解释**。

---

## 一、先说结论（一句话版）

> **前缀和 + HashMap 能处理负数，是因为它不依赖“区间和的单调性”；
> 滑动窗口不行，是因为一旦有负数，窗口和就不再单调变化。**

下面展开。

---

## 二、滑动窗口为什么在「全正数」时可行？

滑动窗口隐含了一个**关键假设**：

* 右指针右移 → 区间和 **只会变大**
* 左指针右移 → 区间和 **只会变小**

这个假设 **只在所有数 ≥ 0 时成立**。

### 典型逻辑

```text
sum < k  → 扩大窗口（right++）
sum > k  → 缩小窗口（left++）
```

这是一个“**可控的单调过程**”。

---

## 三、负数一出现，滑动窗口就崩了 💥

### 举个最小反例

```
nums = [1, -1, 1]
k = 1
```

---

### 滑动窗口尝试

1️⃣ `left=0, right=0`

```
sum = 1 ✔
```

2️⃣ 扩展窗口

```
right=1
sum = 0   （变小了！）
```

3️⃣ 再扩展

```
right=2
sum = 1 ✔
```

现在问题来了：

* `sum < k` 时你 **不知道** 是该扩右还是缩左
* `sum > k` 时缩左 **也可能让 sum 变大**

👉 **决策方向不再可靠**

---

### 本质问题

> 有负数时，
> **移动指针 ≠ 可预测地改变区间和**

滑动窗口失去了“导航能力”。

---

## 四、前缀和 + HashMap 为什么不怕负数？

### 它根本不「移动窗口」

它做的是：

> **固定右端点 i，回头看所有可能的左端点 j**

数学关系：

```
sum[i] - sum[j] = k
```

⇔

```
sum[j] = sum[i] - k
```

---

### 负数完全不影响这个等式

无论 nums 里是：

```
+5, -3, +10, -8, ...
```

这个关系 **永远成立**。

---

## 五、一个负数示例完整走一遍

```
nums = [1, -1, 1]
k = 1
```

### 过程

| i | num | curr_sum | curr_sum - k | map       | 新增子数组    |
| - | --- | -------- | ------------ | --------- | -------- |
| - | -   | 0        | -            | {0:1}     | -        |
| 0 | 1   | 1        | 0            | {0:1}     | [1]      |
| 1 | -1  | 0        | -1           | {0:1,1:1} | -        |
| 2 | 1   | 1        | 0            | {0:2,1:1} | [1,-1,1] |

👉 完全不需要任何“回退”或“调整窗口”。

---

## 六、对比总结（核心差异）

| 维度      | 滑动窗口 | 前缀和 + HashMap |
| ------- | ---- | ------------- |
| 是否依赖单调性 | 是    | 否             |
| 能否处理负数  | ❌    | ✅             |
| 思维方式    | 移动区间 | 数学等式          |
| 本质      | 贪心   | 计数 / 统计       |

---

## 七、什么时候该用哪种？

### 用滑动窗口的前提

* 数组元素 **全是非负**
* 或满足某种 **单调性质**

👉 例如：

* 最小子数组和 ≥ k
* 不重复字符的最长子串

---

### 用前缀和 + HashMap 的信号

* 出现 **负数**
* 问的是 **子数组个数**
* 和、差、等于某个值

👉 **90% 都是前缀和 + 哈希**

---

## 八、一句话终极总结（面试杀手锏）

> 滑动窗口依赖区间和的单调变化，一旦有负数就失效；
> 前缀和方法基于恒等式 `sum[i] - sum[j] = k`，与元素正负无关，因此能稳定处理负数。