Skip to content

Instantly share code, notes, and snippets.

@bigspawn
Last active October 9, 2019 08:10
Show Gist options
  • Save bigspawn/901fc356594e960f14616618c6cd5e16 to your computer and use it in GitHub Desktop.
Save bigspawn/901fc356594e960f14616618c6cd5e16 to your computer and use it in GitHub Desktop.
Задача поиска отрезка (подмассива) массива чисел с заданной суммой
// Задача поиска отрезка (подмассива) массива чисел с заданной суммой
        int findingSum = 11;
        List<Integer> data = List.of(10, -5, 2, 3, -4, 5, 6, 8, -2);
        Map<Integer, Integer> map = new HashMap<>();

        int sum = 0;
        for (int i = 0; i < data.size(); i++) {
            sum += data.get(i);
            map.put(sum, i);
        }

        if (map.containsKey(findingSum)) {
            System.out.println(0 + "," + map.get(findingSum));
            return;
        }
        for (Map.Entry<Integer, Integer> e : map.entrySet()) {
            int halfSum = e.getKey();
            int d = findingSum + halfSum;
            // просматриваем только вправо ->
            if (map.containsKey(d) && map.get(d) > e.getValue()) {
                Integer right = map.get(d);
                int left = e.getValue() + 1; // берем следующий элемент
                System.out.println(left + "," + right);
                return;
            }
        }
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment