题目大意：
查询无效交易
如果出现下述两种情况，交易 可能无效：
- 交易金额超过 ¥1000
- 或者，它和另一个城市中同名的另一笔交易相隔不超过 60 分钟（包含 60 分钟整）
每个交易字符串 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 之间的整数
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1169
解题思路分析：
个人感觉本题出的不是很好，非常不适合在面试中使用。不过既然已经打开题目了，还是分析一下吧。
对于第二个条件，交易金额的判断很简单，关键在于第一个条件，同名异地的两笔交易不超过60分钟。由于本题的数据规模并不大，暴力解是可行的，用两层循环，一一比对每一笔交易，当姓名相同，城市不同，并且交易时间不超过60分钟时，当前2笔交易均为无效交易。比对完所有交易后，也就会统计出所有无效交易。（此算法可以通过所有测试）
接下来，我们可以适当优化一下算法。无效交易的核心是需要同名，如果不是同一人的交易，那么肯定不是我们需要的结果，因此我们可以先将所有数据按照人名进行分组，分组后，再在每一组中按照上面的暴力算法求解，可大幅提高算法效率。
实现代码：
class Data{ // 将每个字符串存储为一个Object
int time; // 交易时间
int amount; // 交易金额
String city; // 城市
String str; // 元字符串
Data(int t, int a, String c,String s){
city=c;
time=t;
amount=a;
str=s;
}
}
public List<String> invalidTransactions(String[] transactions) {
// 按姓名将数据分组
Map<String, List<Data>> map = new HashMap<>();
// 返回结果
Set<String> res = new HashSet<>();
// 循环每个字符串
for(String t : transactions){
// 交易的详细信息
String[] datas = t.split(",");
// 以姓名作为key
String key=datas[0];
// 取得该姓名的所有交易
List<Data> q =map.getOrDefault(key,new ArrayList<>());
// 将当前交易加入列表
q.add(new Data(Integer.parseInt(datas[1]),
Integer.parseInt(datas[2]),
datas[3], t));
map.put(key, q);
}
// 循环每个姓名下的所有交易
for(String key: map.keySet()){
// 当前姓名下的所有交易
List<Data> list = map.get(key);
// 一一比对每一笔交易
for(int i=0;i<list.size();i++){
Data di=list.get(i);
for(int j=i+1;j<list.size();j++){
Data dj=list.get(j);
// 如果交易时间小于等于60并且为异地
if(Math.abs(di.time-dj.time)<=60
&& !di.city.equals(dj.city)){
// 当前两笔交易均为无效交易
res.add(di.str);
res.add(dj.str);
}
}
}
// 找出金额大于1000的交易
for(int i=0;i<list.size();i++){
if(list.get(i).amount>1000){
res.add(list.get(i).str);
}
}
}
return new ArrayList<>(res);
} 本题解法执行时间为20ms。
Runtime: 20 ms, faster than 74.19% of Java online submissions for Invalid Transactions.
Memory Usage: 38 MB, less than 100.00% of Java online submissions for Invalid Transactions.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1169-invalid-transactions-解题思路分析/