收藏清单(双指针

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

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

示例 1:

输入: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] 。
示例 2:

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

输入: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,2,3是否是5,4,3,2,1的子集

这个是可以给两个子集进行排序的,就是变成a=[1,2,3],b=[1,2,3,4,5]

然后用双指针就是定义一个i指针指向a,j指针指向b,首先都等于0(i==0,j==0),然后j进行枚举,就是如a[i]==b[j]就进行i++,j++,就是这样如果i等于a.size(),说明

a中的元素在b中都有,这个就是这个题的难点

class Solution {
public:
    vector<int> peopleIndexes(vector<vector<string>>& strs) {
        int n=strs.size();
        for(auto &l : strs) sort(l.begin(),l.end());
        vector<int>ans;
        for(int i=0;i<n;i++){
            bool flag=false;
            for(int j=0;j<n;j++){
                if(i!=j){
                    auto &A=strs[i],&B=strs[j];
                    int a=0;
                    for(int b=0;b<B.size()&&a<A.size();b++){
                        if(A[a]==B[b]){
                            a++;
                        }
                        if(a==A.size()){
                            flag=true;
                            break;
                        }
                    }
                }
            }
            if(!flag){
                ans.push_back(i);
            }
        }
        return ans;
    }
};
原文地址:https://www.cnblogs.com/lipu123/p/14766580.html