在以下两种情况中，交易 可能无效：
- 交易金额超过
$1000
- 或者，它和 同一个人 在另一个城市 中 的交易相隔不超过
60分钟（包含 60 分钟整）
给定字符串数组交易清单
transaction 。每个交易字符串 transactions[i] 由一些用逗号分隔的值组成，
这些值分别表示交易的人名，时间（以分钟计），金额以及城市。返回可能无效的交易列表。可以按 任何顺序 返回答案。
示例 1：
示例 2：
示例 3：
提示：
transactions.length <= 1000
- 每笔交易
transactions[i]按"{name},{time},{amount},{city}"的格式进行记录
- 每个交易名称
{name}和城市{city}都由小写英文字母组成，长度在1到10之间
- 每个交易时间
{time}由一些数字组成，表示一个0到1000之间的整数
- 每笔交易金额
{amount}由一些数字组成，表示一个0到2000之间的整数
这道题的规则其实很直接。一笔交易无效，有两种情况：
- 金额超过
1000；
- 同一个人在
60分钟内，在不同城市发生了另一笔交易。
交易格式是：
比如：
表示
alice 在时间 20、城市 mtv 发生了一笔金额为 800 的交易。这题的关键不是复杂算法，而是把规则翻译准确。
尤其第二条规则要注意：如果一笔交易和另一笔交易冲突，那么两笔交易都无效。
解法一：暴力枚举
最直接的做法是：对每一笔交易
i，先检查它的金额是否超过 1000；如果超过，直接加入答案。再拿它和所有其他交易
j 比较。只要存在一笔交易满足：同名, 不同城市, 时间差 <= 60 , 那么当前交易 i 就是无效交易。Walk Through Example
假设有两笔交易：
它们名字相同，城市不同，并且时间差是
30 <= 60，所以这两笔交易都无效。
暴力解会在检查第一笔时发现第二笔与它冲突，把第一笔加入答案；
检查第二笔时也会发现第一笔与它冲突，把第二笔加入答案。复杂度分析
- 时间复杂度是
O(n^2)，其中n是交易数量。外层枚举每笔交易，内层最多和所有其他交易比较一次。
- 空间复杂度是
O(n)，主要用于保存解析后的交易数组。结果数组不计入额外空间时，辅助空间也是O(n)。
解法二：按姓名分组
暴力解里有一个明显浪费：如果两笔交易名字不同，它们不可能因为第二条规则互相影响。所以我们可以先按
name 分组。之后只在同一个人的交易列表里做两两比较。先解析每笔交易，并保留它的原始下标。保留下标很重要，因为交易字符串可能重复，例如：
它们是两笔不同交易，不能简单用字符串作为唯一标识。
我们维护一个布尔数组
invalid[i] = 第 i 笔交易是否无效金额超过
1000 的交易直接标记为无效。然后对每个名字对应的交易列表，做两两比较。如果两笔交易城市不同，并且时间差不超过
60，就把它们都标记为无效。最后按原始顺序返回所有
invalid[i] == True 的交易字符串。复杂度分析
- 时间复杂度: 最坏仍然是
O(n^2)。
这个优化不改变最坏复杂度，因为极端情况下所有交易都属于同一个人，分组后依然要比较所有交易对，仍然是
O(n^2)。但在真实数据里，如果交易分散在不同用户之间，比较次数会少很多。- 空间复杂度:
O(n)，用于保存解析后的交易、分组哈希表和无效标记数组。
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-1169-无效交易
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
上一篇
[Leetcode 729] 日程安排 1
下一篇
Production Agents Need Workflow Graphs