Medium

题目描述

一个交易可能无效，如果：

  • 金额超过 $1000，或者
  • 它在同一个人的另一笔不同城市的交易的 60 分钟内（包括 60 分钟）发生。

给你一个字符串数组 transaction，其中 transactions[i] 由逗号分隔的值组成，表示交易的姓名、时间（以分钟为单位）、金额和城市。

返回可能无效的交易列表。你可以按任何顺序返回答案。

示例 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 之间的整数

解题思路

这道题需要检查每笔交易是否符合两个无效条件：

解题思路：

  1. 解析交易数据：首先需要将每个交易字符串解析成结构化数据，提取姓名、时间、金额和城市信息。

  2. 检查无效条件：

    • 条件1：金额超过1000直接无效
    • 条件2：同名但不同城市的交易在60分钟内发生

  3. 算法实现：

    • 将所有交易解析并存储
    • 对每笔交易，检查金额是否超过1000
    • 对每笔交易，遍历所有其他交易，检查是否存在同名、不同城市且时间差≤60分钟的交易
    • 使用集合避免重复添加无效交易

优化思路：

  • 可以按姓名分组来减少比较次数
  • 使用哈希表存储解析后的交易信息
  • 时间复杂度为O(N²)，空间复杂度为O(N)

这种方法直观且易于实现，虽然时间复杂度较高，但在给定约束条件下（N≤1000）完全可以接受。

代码实现

class Solution {
public:
    vector<string> invalidTransactions(vector<string>& transactions) {
        vector<vector<string>> parsed;
        for (const string& t : transactions) {
            vector<string> parts;
            stringstream ss(t);
            string part;
            while (getline(ss, part, ',')) {
                parts.push_back(part);
            }
            parsed.push_back(parts);
        }
        
        set<int> invalid;
        
        for (int i = 0; i < transactions.size(); i++) {
            int amount = stoi(parsed[i][2]);
            if (amount > 1000) {
                invalid.insert(i);
            }
            
            for (int j = 0; j < transactions.size(); j++) {
                if (i != j && parsed[i][0] == parsed[j][0] && parsed[i][3] != parsed[j][3]) {
                    int time1 = stoi(parsed[i][1]);
                    int time2 = stoi(parsed[j][1]);
                    if (abs(time1 - time2) <= 60) {
                        invalid.insert(i);
                        invalid.insert(j);
                    }
                }
            }
        }
        
        vector<string> result;
        for (int idx : invalid) {
            result.push_back(transactions[idx]);
        }
        
        return result;
    }
};

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        parsed = []
        for t in transactions:
            parts = t.split(',')
            parsed.append(parts)
        
        invalid = set()
        
        for i in range(len(transactions)):
            amount = int(parsed[i][2])
            if amount > 1000:
                invalid.add(i)
            
            for j in range(len(transactions)):
                if i != j and parsed[i][0] == parsed[j][0] and parsed[i][3] != parsed[j][3]:
                    time1 = int(parsed[i][1])
                    time2 = int(parsed[j][1])
                    if abs(time1 - time2) <= 60:
                        invalid.add(i)
                        invalid.add(j)
        
        result = []
        for idx in invalid:
            result.append(transactions[idx])
        
        return result

public class Solution {
    public IList<string> InvalidTransactions(string[] transactions) {
        var parsed = new List<string[]>();
        foreach (string t in transactions) {
            parsed.Add(t.Split(','));
        }
        
        var invalid = new HashSet<int>();
        
        for (int i = 0; i < transactions.Length; i++) {
            int amount = int.Parse(parsed[i][2]);
            if (amount > 1000) {
                invalid.Add(i);
            }
            
            for (int j = 0; j < transactions.Length; j++) {
                if (i != j && parsed[i][0] == parsed[j][0] && parsed[i][3] != parsed[j][3]) {
                    int time1 = int.Parse(parsed[i][1]);
                    int time2 = int.Parse(parsed[j][1]);
                    if (Math.Abs(time1 - time2) <= 60) {
                        invalid.Add(i);
                        invalid.Add(j);
                    }
                }
            }
        }
        
        var result = new List<string>();
        foreach (int idx in invalid) {
            result.Add(transactions[idx]);
        }
        
        return result;
    }
}

var invalidTransactions = function(transactions) {
    const invalid = new Set();
    const parsed = transactions.map(t => {
        const [name, time, amount, city] = t.split(',');
        return { name, time: parseInt(time), amount: parseInt(amount), city, original: t };
    });
    
    for (let i = 0; i < parsed.length; i++) {
        const t1 = parsed[i];
        
        // Check if amount exceeds $1000
        if (t1.amount > 1000) {
            invalid.add(t1.original);
        }
        
        // Check for transactions within 60 minutes in different city
        for (let j = 0; j < parsed.length; j++) {
            if (i !== j) {
                const t2 = parsed[j];
                if (t1.name === t2.name && 
                    Math.abs(t1.time - t2.time) <= 60 && 
                    t1.city !== t2.city) {
                    invalid.add(t1.original);
                    break;
                }
            }
        }
    }
    
    return Array.from(invalid);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(N²)
空间复杂度O(N)

说明：

  • 时间复杂度：需要对每个交易检查所有其他交易，因此是O(N²)
  • 空间复杂度：存储解析后的交易数据和无效交易索引，空间复杂度为O(N)