LeetCode 1169 查询无效交易-EW帮帮网

攻克 “找出可能无效交易列表” 问题：Java 实战解析

在当今数字化时代，金融交易系统时刻处理着海量的交易数据。为了保障交易的安全性与合理性，系统需要实时检测异常交易。本文要探讨的 “找出可能无效交易列表” 问题，就来源于金融交易场景。借助解决这个问题，我们能深入理解如何运用 Java 语言，巧妙地设计算法和数据结构，实现对复杂业务逻辑的处理。

一、问题描述

在交易过程中，一旦出现以下两种情况，交易就可能无效：

交易金额超阈值：交易金额超过 1000 美元。
异地同名近时交易：和另一个城市中同名的另一笔交易，时间间隔不超过 60 分钟（包含 60 分钟整）。

系统会给出一个字符串数组形式的交易清单 transactions，每个交易字符串 transactions[i] 由逗号分隔，依次记录了交易的名称、时间（以分钟计）、金额以及城市。我们的任务就是找出所有可能无效的交易，并以任意顺序返回结果。

二、问题分析

2.1 数据解析

每个交易记录都是一个字符串，我们首先要做的，就是把这个字符串解析成各个独立的属性，提取出交易的名称、时间、金额和城市信息，方便后续操作。因为这些信息在后续判断交易是否有效时都会用到，比如金额用于判断是否超过 1000 美元，城市和时间用于判断是否满足 “异地同名近时交易” 的条件。

2.2 条件检查

针对每一笔交易，我们需要分别检查它是否满足上述两种无效交易的条件。对于 “交易金额超阈值” 的条件，比较简单直接，只需要将交易金额与 1000 进行比较即可。而在检查 “异地同名近时交易” 条件时，需要快速找到同名的所有交易记录，并进行时间和城市信息的比对。这就需要一种合适的数据结构来存储和管理这些交易记录，以便高效地进行查找和判断。

2.3 数据结构选择

为了实现快速查找同名交易记录，我们可以使用 Map 数据结构。将交易的名称作为键，把该名称对应的所有交易记录存储在一个列表中，作为 Map 的值。这样，当我们需要检查某笔交易是否与其他城市中同名交易在时间上满足条件时，就可以通过交易名称快速定位到该名称下的所有交易记录，然后进行逐一检查，极大地提高了查找效率。

三、代码实现

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<String> invalidTransactions(String[] transactions) {
        List<String> invalid = new ArrayList<>();
        Map<String, List<Transaction>> nameToTransactions = new HashMap<>();

        // 解析交易信息并存储到映射中
        for (String transaction : transactions) {
            Transaction t = new Transaction(transaction);
            nameToTransactions.computeIfAbsent(t.name, k -> new ArrayList<>()).add(t);
        }

        // 检查每笔交易是否无效
        for (String transaction : transactions) {
            Transaction t = new Transaction(transaction);
            boolean isInvalid = false;

            // 检查交易金额是否超过1000
            if (t.amount > 1000) {
                isInvalid = true;
            }

            // 检查是否和另一个城市中同名的另一笔交易相隔不超过60分钟
            for (Transaction other : nameToTransactions.get(t.name)) {
                if (!other.city.equals(t.city) && Math.abs(other.time - t.time) <= 60) {
                    isInvalid = true;
                    break;
                }
            }

            if (isInvalid) {
                invalid.add(transaction);
            }
        }

        return invalid;
    }

    // 定义交易类
    class Transaction {
        String name;
        int time;
        int amount;
        String city;

        Transaction(String transaction) {
            String[] parts = transaction.split(",");
            this.name = parts[0];
            this.time = Integer.parseInt(parts[1]);
            this.amount = Integer.parseInt(parts[2]);
            this.city = parts[3];
        }

        @Override
        public String toString() {
            return name + "," + time + "," + amount + "," + city;
        }
    }
}

四、代码说明

4.1 Transaction 类

Transaction 类用于表示单个交易记录，包含交易的名称、时间、金额和城市四个属性。构造函数接收一个交易字符串，通过 split 方法按逗号进行分割，将各个部分解析为对应的属性。这里需要注意的是，在解析时间和金额时，使用了 Integer.parseInt 方法将字符串转换为整数类型，以便后续进行数值比较。toString 方法则方便将交易对象转换回字符串形式，便于调试和输出，也符合题目中交易记录以字符串形式输入和输出的要求。

4.2 nameToTransactions 映射

nameToTransactions 是一个 Map，键为交易名称，值为该名称对应的交易记录列表。computeIfAbsent 方法的使用，确保了在向映射中添加交易记录时，如果该名称对应的列表不存在，会自动创建一个新的列表，避免了繁琐的空指针检查。这是 Java 8 引入的一个非常实用的方法，大大简化了代码逻辑，提高了代码的可读性和健壮性。

4.3 解析交易信息

通过遍历输入的 transactions 数组，将每个交易字符串解析为 Transaction 对象，并添加到 nameToTransactions 映射中，完成交易信息的初步处理，为后续的无效交易检查做好准备。这个过程是整个算法的基础，只有准确地解析和存储了交易信息，才能正确地进行后续的判断。

4.4 检查交易是否无效

再次遍历 transactions 数组，对于每一笔交易，首先检查交易金额是否超过 1000 美元，如果超过则直接标记为无效，通过设置 isInvalid 为 true 来表示。接着，从 nameToTransactions 映射中获取同名的所有交易记录，遍历这些记录，检查是否存在与当前交易城市不同且时间间隔不超过 60 分钟的交易。一旦找到符合条件的交易，就标记当前交易为无效，并使用 break 语句跳出循环，因为只要满足其中一个无效条件，该交易就已经被判定为无效，不需要再继续检查其他同名交易记录了。

4.5 返回结果

将所有标记为无效的交易字符串添加到 invalid 列表中，并返回该列表，完成整个无效交易查找过程。最终返回的列表就是我们根据题目要求找出的所有可能无效的交易记录。

五、时间和空间复杂度分析

5.1 时间复杂度

解析交易信息阶段：遍历一次交易字符串数组，时间复杂度为 $O(n)$ ，n 为交易数量。因为对于每个交易字符串，都需要进行一次分割和属性提取操作，这些操作的时间复杂度都是常数级别的，所以总的时间复杂度与交易数量成正比。
检查交易是否无效阶段：对于每一笔交易，最多需要遍历所有同名的交易记录。假设同名交易的平均数量为 m，那么这部分的时间复杂度为 $O(n\times m)$ 。因为对于每个交易，都需要在同名交易记录列表中进行查找和比较操作，而这些操作的时间复杂度与列表长度成正比。综合来看，总的时间复杂度为 $O(n\times m)$ 。

5.2 空间复杂度

nameToTransactions 映射：用于存储所有交易记录，假设每个交易记录占用的空间为常数，那么它的空间复杂度为 $O(n)$ 。因为映射中存储的交易记录数量与输入的交易数量相同，所以空间复杂度与交易数量成正比。
invalid 列表：用于存储无效交易记录，其空间复杂度同样为 $O(n)$ 。因为在最坏情况下，所有交易都可能是无效的，所以该列表的长度最大为交易数量 n。因此，总的空间复杂度为 $O(n)$ 。

通过以上全面的分析和实现，我们不仅成功解决了找出可能无效交易列表的问题，还对代码的时间和空间复杂度有了深入的理解。这不仅有助于我们在实际开发中优化代码性能，还能提升解决复杂问题的能力。希望本文能为大家在算法学习和实际开发中提供有益的参考。

LeetCode 1169 查询无效交易