题目描述

给你一个数组 favoriteCompanies ，其中 favoriteCompanies[i] 是第 i 名用户收藏的公司清单（下标从 0 开始）。

请找出不是其他任何人收藏的公司清单的子集的收藏清单，并返回该清单下标。下标需要按升序排列。

样例

输入：favoriteCompanies = [["leetcode","google","facebook"],["google","microsoft"],["google","facebook"],["google"],["amazon"]]
输出：[0,1,4] 
解释：
favoriteCompanies[2]=["google","facebook"] 是 favoriteCompanies[0]=["leetcode","google","facebook"] 的子集。
favoriteCompanies[3]=["google"] 是 favoriteCompanies[0]=["leetcode","google","facebook"] 和 favoriteCompanies[1]=["google","microsoft"] 的子集。
其余的收藏清单均不是其他任何人收藏的公司清单的子集，因此，答案为 [0,1,4] 。

输入：favoriteCompanies = [["leetcode","google","facebook"],["leetcode","amazon"],["facebook","google"]]
输出：[0,1] 
解释：favoriteCompanies[2]=["facebook","google"] 是 favoriteCompanies[0]=["leetcode","google","facebook"] 的子集，因此，答案为 [0,1] 。

输入：favoriteCompanies = [["leetcode"],["google"],["facebook"],["amazon"]]
输出：[0,1,2,3]

提示：

• 1 <= favoriteCompanies.length <= 100
• 1 <= favoriteCompanies[i].length <= 500
• 1 <= favoriteCompanies[i][j].length <= 20
• favoriteCompanies[i] 中的所有字符串 各不相同 。
• 用户收藏的公司清单也 各不相同 ，也就是说，即便我们按字母顺序排序每个清单， favoriteCompanies[i] != favoriteCompanies[j] 仍然成立。
• 所有字符串仅包含小写英文字母。

算法分析

• 1、判断某个清单A是否是其他清单B的子集，也就是是否存在B包含A，若包含A则表示A不符合条件
• 2、枚举所有清单A，再枚举所有清单B，判断B是否包含A的所有元素，如何判断？将B的所有元素加入到HashSet中，判断HashSet是否包含A的所有元素

时间复杂度 $O(n^3)$

两重循环 和 放进hash表操作

Java 代码

class Solution {
    public List<Integer> peopleIndexes(List<List<String>> favoriteCompanies) {
        List<Integer> ans = new ArrayList<Integer>();
        int n = favoriteCompanies.size();
        for(int i = 0;i < favoriteCompanies.size();i ++)
        {
            List<String> one = favoriteCompanies.get(i);
            boolean success = true;//标记是否需要加到ans中，若为false表示该清单是其他清单的子集
            for(int j = 0;j < favoriteCompanies.size();j ++)
            {
                List<String> two = favoriteCompanies.get(j);
                if(i == j) continue;
                HashSet<String> set = new HashSet<String>(two);
                if(set.containsAll(one))
                {
                    success = false;
                    break;
                }
            }
            if(success) ans.add(i);
        }
        return ans;
    }
}