题目描述

(通过次数2,221 | 提交次数4,140,通过率53.65%)

表名: Friendship
+-------------+------+
| 列名         | 类型 |
+-------------+------+
| user1_id    | int  |
| user2_id    | int  |
+-------------+------+
(user1_id, user2_id) 是这个表的主键。
这张表的每一行都表示用户 user1_id 和 user2_id 是朋友。
请注意,user1_id < user2_id。
如果 x 和y为朋友且他们至少有三个共同的朋友 ,那么x 和y 之间的友谊就是坚定的。
写一个 SQL 查询来找到所有的坚定的友谊。
注意,结果表不应该包含重复,并且 user1_id < user2_id。
以任何顺序返回结果表。
查询结果的格式在下面的例子中。
示例1:
输入: 
表 Friendship:
+----------+----------+
| user1_id | user2_id |
+----------+----------+
| 1        | 2        |
| 1        | 3        |
| 2        | 3        |
| 1        | 4        |
| 2        | 4        |
| 1        | 5        |
| 2        | 5        |
| 1        | 7        |
| 3        | 7        |
| 1        | 6        |
| 3        | 6        |
| 2        | 6        |
+----------+----------+
输出: 
+----------+----------+---------------+
| user1_id | user2_id | common_friend |
+----------+----------+---------------+
| 1        | 2        | 4             |
| 1        | 3        | 3             |
+----------+----------+---------------+
解释: 
用户 1 和 2 有 4 个共同的朋友(3,4,5,和 6)。
用户 1 和 3 有 3 个共同的朋友(2,6,和 7)。
我们没有包括用户 2 和 3 的友谊,因为他们只有两个共同的朋友(1 和 6)。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/strong-friendship
//测试数据
Create table If Not Exists Friendship (user1_id int, user2_id int);

insert into Friendship (user1_id, user2_id) values ('1', '2');
insert into Friendship (user1_id, user2_id) values ('1', '3');
insert into Friendship (user1_id, user2_id) values ('2', '3');
insert into Friendship (user1_id, user2_id) values ('1', '4');
insert into Friendship (user1_id, user2_id) values ('2', '4');
insert into Friendship (user1_id, user2_id) values ('1', '5');
insert into Friendship (user1_id, user2_id) values ('2', '5');
insert into Friendship (user1_id, user2_id) values ('1', '7');
insert into Friendship (user1_id, user2_id) values ('3', '7');
insert into Friendship (user1_id, user2_id) values ('1', '6');
insert into Friendship (user1_id, user2_id) values ('3', '6');
insert into Friendship (user1_id, user2_id) values ('2', '6');

解题思路

从本质上来说,这道题跟1951. 查询具有最多共同关注者的所有两两结对组是一样的。

都是计算两两之间的交集的个数。

不一样的是,在原始业务场景下,题目1951的关系是单向的。而本题的关系是双向的。

也就是说,在题目1951中,1关注了2,但2不一定关注了1。而本题中,1和2是好友,同时,2和1当然也是好友。

既然关系是双向的,那么我们在处理之前,是不是可以把双向的关系都生成出来呢?

像下面这样:

select user1_id,user2_id from Friendship
union all
select user2_id as user1_id,user1_id as user2_id from Friendship;

剩下的解题思路,就和题目1951相同了。

不过,这里需要注意的一点是,在使用笛卡尔积生成两两关系后,需要把两两之间不是好友的数据排除掉(如果1和2本身就不是好友,那么也就不需要计算他们之间共同的好友了)。否则可能会生成错误的数据。

参考SQL

未特别说明的情况下,参考SQL为基于MySQL8.0实现。
with
tmp as (
    select user1_id,user2_id from Friendship
    union all
    select user2_id as user1_id,user1_id as user2_id from Friendship
)
select
    a.user1_id,b.user1_id user2_id,count(1) common_friend
from tmp a
inner join tmp b
on a.user2_id = b.user2_id
and a.user1_id < b.user1_id
where (a.user1_id,b.user1_id) in (select c.user1_id,c.user2_id from Friendship c)
group by a.user1_id,b.user1_id
having count(1)>=3
order by a.user1_id,b.user1_id;
picture loss