Как проверить, является ли список подмножеством другого списка в java?

Подход к решению этой проблемы очень похож на решение проблемы сопоставления подстрок.

Вы начинаете с проверки первого элемента списка предположительно подмножества (далее именуемого как SSL).

Как только вы получите совпадение, обратите внимание на индекс (далее будет называться myGuy в основном списке, где найдено совпадение, перейдите к проверке, соответствуют ли последующие элементы SSL основному списку.

Если ваш матч завершен, просто вернитесь. Если нет, то можно сделать одно из двух. Если в основном списке остались элементы, увеличьте myGuy, и тогда он станет новым индексом, с которого вы начинаете итерацию в основном списке.
Если элементов не осталось, а полного совпадения нет, тогда это не подмножество.

Вот как вы можете сделать это в Java:

private static boolean checkSubList(int[] mainList, int[] subList) {
    int currentIteratingPointer;
    int matchCounter = 0;

    for (int i = 0; i < mainList.length; i++) {
        currentIteratingPointer = i;
        for (int j = 0; j < subList.length; j++) {
            if (mainList[currentIteratingPointer] == subList[j]) {
                System.out.println(mainList[currentIteratingPointer]);
                ++matchCounter;
                ++currentIteratingPointer;
            } else {
                --matchCounter;
                break;
            }
        }

        i = currentIteratingPointer;
    }

    return matchCounter == subList.length; // You can count the number of occurance of the sublist if you change
    // it to int and return the matchCounter a
}

Проблема в том, что contains для Set было бы хорошо (для уникальных чисел), но для List наивный contains требует двух вложенных циклов, квадратичной сложности O(N²): для двух списков из 100 элементов потребуется 10 000 шагов. Следовательно, нужно либо преобразовать списки в наборы, либо сортировать списки.

Сортировка списка может быть O (N log N), но для связанного списка, как вам кажется, он остается прежним:

public ItemsList sort(ItemsList list) {
    ItemsList sortedList = new ItemsList();
    for (ItemNode node : list) {
        sortedList.insertSorted(node.item);
    }
    return sortedList;
}

Но после сортировки вы могли бы сделать, как вы сказали, с линейной сложностью O (N).

public boolean contains(ItemsList ilist) {
    ItemsList sortedThis = this.sorted();
    ItemsList sortedOther = iList.sorted();
    ItemNode node = sortedThis.first;
    ItemNode other = otherList.first;
    while (node != null) {
        if (other == null) {
            break; // return true;
        }
        if (other.item < node.item) {
            break; // return false;
        }
        if (other.item == node.item) {
            other = other.next; // Match found.
        }
        node = node.next;
    }
    return other == null;
}

Поскольку списки могут содержать дубликаты, используйте сортировку.

Итак, в основном вы хотите найти анаграммы одного списка в другом.

вот моя реализация для строковых анаграмм

abcde, dbc -> истина

Ознакомьтесь с моим кодом и попробуйте реализовать его в вашем случае использования.

public boolean findStringAnagrams(String str, String pattern) {


        Map<Character, Integer> charMap = new HashMap<>();
        for (int i = 0; i < pattern.length(); i++) {
            charMap.put(pattern.charAt(i), charMap.getOrDefault(pattern.charAt(i), 0) + 1);
        }

        Integer windowStart = pattern.length() - 1;
        for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {

            Character c = str.charAt(windowEnd);
            charMap.computeIfPresent(c, (key, val) -> val - 1);
            if (charMap.containsKey(c) && charMap.get(c) == 0)
                charMap.remove(c);

            if (windowStart < windowEnd) {

                if (charMap.size() == 0) {
                    return true;
                }
                charMap.put(str.charAt(windowStart), charMap.getOrDefault(str.charAt(windowStart), 0) + 1);
                windowStart++;
            }

        }

        return false;
    }

Попробуйте этот источник

public class ListTest {

    List small = new ArrayList<>();
    List big = new ArrayList<>();

    public static void main(String args[]) {
        ListTest g = new ListTest();

        g.populateList();
        boolean bFlag = g.checkIfSubset();
        System.out.println("====is subset====>" + bFlag);
    }

    private boolean checkIfSubset() {
        for (Object in : small) {
            if (!big.contains(in)) {
                return false;
            }
        }
        return true;
    }

    private void populateList() {
        small.add(11);
        small.add(23);

        big.add(11);
        big.add(2);
        big.add(23);
        big.add(24);
    }

}