LeetCode 题解工作台
查询无效交易
如果出现下述两种情况，交易 可能无效 ： 交易金额超过 $1000 或者，它和 另一个城市 中 同名 的另一笔交易相隔不超过 60 分钟（包含 60 分钟整） 给定字符串数组交易清单 transaction 。每个交易字符串 transactions[i] 由一些用逗号分隔的值组成，这些值分别表示交…
4
题型
4
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
遍历交易列表，对于每笔交易，如果金额大于 1000，或者同名且城市不同且时间间隔不超过 60 分钟，则将其加入答案。 具体地，我们使用哈希表 `d` 记录每个交易，其中键为交易名称，值为一个列表，列表中的每个元素为一个三元组 `(time, city, index)`，表示在 `time` 时刻在 `city` 城市进行了编号为 `index` 的交易。同时，我们使用哈希表 `idx` 记录答案中…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
如果出现下述两种情况，交易 可能无效：
- 交易金额超过
$1000 - 或者，它和 另一个城市 中 同名 的另一笔交易相隔不超过
60分钟（包含 60 分钟整）
给定字符串数组交易清单 transaction 。每个交易字符串 transactions[i] 由一些用逗号分隔的值组成，这些值分别表示交易的名称，时间（以分钟计），金额以及城市。
返回 transactions，返回可能无效的交易列表。你可以按 任何顺序 返回答案。
示例 1：
输入：transactions = ["alice,20,800,mtv","alice,50,100,beijing"] 输出：["alice,20,800,mtv","alice,50,100,beijing"] 解释：第一笔交易是无效的，因为第二笔交易和它间隔不超过 60 分钟、名称相同且发生在不同的城市。同样，第二笔交易也是无效的。
示例 2：
输入：transactions = ["alice,20,800,mtv","alice,50,1200,mtv"] 输出：["alice,50,1200,mtv"]
示例 3：
输入：transactions = ["alice,20,800,mtv","bob,50,1200,mtv"] 输出：["bob,50,1200,mtv"]
提示：
transactions.length <= 1000- 每笔交易
transactions[i]按"{name},{time},{amount},{city}"的格式进行记录 - 每个交易名称
{name}和城市{city}都由小写英文字母组成，长度在1到10之间 - 每个交易时间
{time}由一些数字组成，表示一个0到1000之间的整数 - 每笔交易金额
{amount}由一些数字组成，表示一个0到2000之间的整数
解题思路
方法一：哈希表 + 模拟
遍历交易列表，对于每笔交易，如果金额大于 1000，或者同名且城市不同且时间间隔不超过 60 分钟，则将其加入答案。
具体地，我们使用哈希表 d 记录每个交易，其中键为交易名称，值为一个列表，列表中的每个元素为一个三元组 (time, city, index)，表示在 time 时刻在 city 城市进行了编号为 index 的交易。同时，我们使用哈希表 idx 记录答案中的交易编号。
遍历交易列表，对于每笔交易，我们首先将其加入哈希表 d 中，然后判断其金额是否大于 1000，如果是，则将其编号加入答案中。然后我们遍历哈希表 d 中的交易，如果交易名称相同且城市不同且时间间隔不超过 60 分钟，则将其编号加入答案中。
最后，我们遍历答案中的交易编号，将其对应的交易加入答案即可。
时间复杂度 ，空间复杂度 。其中 为交易列表的长度。
class Solution:
def invalidTransactions(self, transactions: List[str]) -> List[str]:
d = defaultdict(list)
idx = set()
for i, x in enumerate(transactions):
name, time, amount, city = x.split(",")
time, amount = int(time), int(amount)
d[name].append((time, city, i))
if amount > 1000:
idx.add(i)
for t, c, j in d[name]:
if c != city and abs(time - t) <= 60:
idx.add(i)
idx.add(j)
return [transactions[i] for i in idx]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n^2) in the worst case due to pairwise comparisons per name, but splitting and hash lookups reduce overhead. Space complexity is O(n) for storing transactions per name in hash tables. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Checks if you can efficiently scan arrays while tracking past transactions with hash maps.
- question_mark
Wants you to correctly handle both amount threshold and cross-city time conflicts simultaneously.
- question_mark
May probe about optimizing nested loops or reducing redundant comparisons per user.
常见陷阱
外企场景- error
Forgetting to compare transactions only with the same name, causing false positives.
- error
Ignoring the 60-minute window or miscalculating the difference between transaction times.
- error
Failing to preserve the original transaction string in the output while returning results.
进阶变体
外企场景- arrow_right_alt
Identify invalid transactions with a dynamic threshold instead of fixed 1000 amount.
- arrow_right_alt
Handle transactions across multiple cities with variable time windows.
- arrow_right_alt
Return transactions grouped by user instead of a flat list for further processing.