查询无效交易

难度: Medium

如果出现下述两种情况，交易 可能无效：

交易金额超过 $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 之间的整数

Submission

运行时间: 47 ms

内存: 16.5 MB

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        name = {}
        for t in transactions:
            a,b,c,d = t.split(',')
            if a in name:
                name[a].append([int(b),d])
            else:
                name[a] = [[int(b),d]]
                
        ans = []
        for t in transactions:
            a,b,c,d = t.split(',')
            if int(c) > 1000:
                ans.append(t)
            else:
                lis = name[a]
                for x,y in lis:
                    if abs(x-int(b)) <= 60 and y != d:
                        ans.append(t)
                        break
        return ans
                
'''
        for ls in name:
            name[ls].sort()
            print(name[ls])
            '''

Explain

这个题解使用了哈希表来跟踪每个人的交易记录，并检查每个交易是否有效。首先，通过遍历每个交易字符串，它解析出交易者的姓名、时间、金额和城市，并将时间和城市存储在哈希表中，键为交易者姓名。之后，再次遍历每个交易，首先检查交易金额是否超过1000美元，如果是，则将其添加到无效交易列表中。接着，对于没有直接因金额超标而无效的交易，它会检查同一个人的其他交易记录，看是否有在不同城市且时间差在60分钟以内的交易，如果有，该交易也被认为是无效的。这个方法保证了能检测出题目中定义的所有无效交易情况。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        name = {}
        # 建立哈希表，存储每个交易者的交易记录
        for t in transactions:
            a, b, c, d = t.split(',')
            if a in name:
                name[a].append([int(b), d])
            else:
                name[a] = [[int(b), d]]

        ans = []
        # 检查每一笔交易是否无效
        for t in transactions:
            a, b, c, d = t.split(',')
            if int(c) > 1000:
                ans.append(t)
            else:
                lis = name[a]
                for x, y in lis:
                    if abs(x - int(b)) <= 60 and y != d:
                        ans.append(t)
                        break
        return ans

Explore

是的，当前算法的效率可能较低，因为它对每个交易进行了遍历，并且对每个交易再次遍历该交易者的所有交易记录来检查条件，这使得时间复杂度接近O(n^2)，其中n是交易的数量。可以通过以下方式优化算法：1. 使用更复杂的数据结构，例如哈希表中不仅存储时间和城市，还可以存储交易索引和金额，这样可以更快速地进行查找和比较。2. 对每个交易者的交易记录按时间排序，然后使用两个指针的方法来检查60分钟内的其他交易，这样可以减少不必要的比较，从而提高效率。

是的，存在重复交易被多次添加到结果列表中的可能性。例如，如果一笔交易因为金额超过1000美元而被添加到结果中，而后又因为与另一笔交易在不同城市且时间差在60分钟内被再次添加，这就导致了重复。为了避免这种情况，可以在添加到结果列表之前检查该交易是否已经存在于结果中。更有效的方法是使用集合（Set）来存储结果，因为集合自动处理重复项，这样即使尝试添加重复的交易，也不会在结果集合中重复出现。