问题描述

编写一个函数，该函数接受两个列表作为参数，判断第一个列表是否是第二个列表的顺序子集，返回True或False。

要求

1. 判断一个列表是否是另一个列表的顺序子集，即第一个列表的所有元素在第二个列表需要顺序出现。
2. 列表中的元素可以是任意类型，包括整数、字符串、对象等。
3. 两个列表中的元素可以重复，需要先做顺序递增排序。
4. 如果第一个列表为空，则返回True。

测试代码

assert isSubset(Arrays.asList(1, 2, 3), Arrays.asList(1, 2, 3, 4, 5)) == true;
assert isSubset(Arrays.asList(1, 2, 3), Arrays.asList(1, 2, 3)) == true;
assert isSubset(Arrays.asList(1, 3, 2), Arrays.asList(1, 2, 3, 4)) == true;
assert isSubset(Arrays.asList(1, 2, 3), Arrays.asList(1, 2, 4, 5)) == false;
assert isSubset(Arrays.asList(1, 2, 3), Arrays.asList(1, 2, 2, 3, 3)) == false;
assert isSubset(Arrays.asList(1, 2, 3), Arrays.asList(1, 2)) == false;
assert isSubset(Arrays.asList(), Arrays.asList(1, 2, 3)) == true;
assert isSubset(Arrays.asList(1, 2, 3), Arrays.asList(0, 1, 2, 3)) == true;

解决思路

这个相当于最简单的子集问题，我们可以使用两个循环来实现，分别遍历两个列表，判断第一个列表的元素是否按照顺序出现在第二个列表中。 可以先对两个列表进行排序，然后再进行比较

代码实现

    public static boolean isSubset(List<Object> partList, List<Object> fullList) {
        if (partList.isEmpty()) {
            return true;
        }
        partList.sort((a, b) -> a.hashCode() - b.hashCode());
        fullList.sort((a, b) -> a.hashCode() - b.hashCode());

        int i = 0;
        int j = 0;
        while (i < partList.size() && j < fullList.size()) {
            if (partList.get(i).equals(fullList.get(j))) {
                i++;
            } else if (i > 0) {
                return false;
            }
            j++;
        }
        return i == partList.size();
    }

完整代码请参考:

总结

这个问题是后端开发中常见的问题，我们可以使用两个循环来实现，如果列表很大，效率会比较低，但是代码比较简单好用

作为后端开发工程师，我们需要了解列表的常用操作和应用场景，这样才能更好地优化代码，提高系统的性能。

所有的后端面试常见的问题，我们每天都会在我们的编程群里面讨论和Code review, 欢迎大家加入我们的编程群，一起学习和进步。

欢迎大家关注 入职啦 (公众号: ruzhila) ，获取更多有趣的编程挑战题和技术干货！