题目

给你一个无向图，整数 n 表示图中节点的数目，edges 数组表示图中的边，

其中 edges[i] = [ui, vi] ，表示 ui 和 vi 之间有一条无向边。

一个 连通三元组 指的是 三个 节点组成的集合且这三个点之间 两两 有边。

连通三元组的度数 是所有满足此条件的边的数目：一个顶点在三元组内，而另一个顶点不在三元组内。

请你返回所有连通三元组中度数的 最小值 ，如果图中没有连通三元组，那么返回 -1 。

示例 1：输入：n = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]] 输出：3

解释：只有一个三元组 [1,2,3] 。构成度数的边在上图中已被加粗。

示例 2：输入：n = 7, edges = [[1,3],[4,1],[4,3],[2,5],[5,6],[6,7],[7,5],[2,6]] 输出：0

解释：有 3 个三元组：

1) [1,4,3]，度数为 0 。

2) [2,5,6]，度数为 2 。

3) [5,6,7]，度数为 2 。

提示：2 <= n <= 400

edges[i].length == 2

1 <= edges.length <= n * (n-1) / 2

1 <= ui, vi <= n

ui != vi

图中没有重复的边。

解题思路分析

1、暴力法；时间复杂度O(n^3)，空间复杂度O(n)

func minTrioDegree(n int, edges [][]int) int {
	arr := make([]int, 401)
	m := make(map[int]bool)
	for i := 0; i < len(edges); i++ {
		a, b := edges[i][0], edges[i][1]
		arr[a]++
		arr[b]++
		m[getValue(a, b)] = true
	}
	res := math.MaxInt32
	for i := 1; i < n-1; i++ {
		for j := i + 1; j < n; j++ {
			if m[getValue(i, j)] == true {
				for k := j + 1; k <= n; k++ {
					if m[getValue(i, k)] == true && m[getValue(j, k)] == true {
						if arr[i]+arr[j]+arr[k]-6 < res {
							res = arr[i] + arr[j] + arr[k] - 6
						}
					}
				}
			}
		}
	}
	if res == math.MaxInt32 {
		return -1
	}
	return res
}

总结

Medium题目，采用暴力法思路可以过，分别判断