Последовательность с суммой K

средне

# решено

Дан неотсортированный массив nums целых чисел и число k. Необходимо найти непрерывный подмассив, сумма элементов которого равна k.

Нужно вернуть массив из двух элементов — индексы начала и конца любого подходящего подмассива. Если такого подмассива не существует, вернуть [-1, -1].

Пример 1:

Ввод: nums = [9, -6, 5, 3, 2, 7], k = 10
Вывод: [2, 4]
Объяснение: подмассив [5, 3, 2] начинается с индекса 2 и заканчивается на индексе 4, сумма равна 10.

Пример 2:

Ввод: nums = [1, 2, 3], k = 7
Вывод: [-1, -1]

Пример 3:

Ввод: nums = [1, 2, 5, 7], k = 7
Вывод: [1, 2]
Объяснение: существует 2 подмассива с суммой 7: [2, 5] (индексы 1-2) и [7] (индекс 3). Подходит любой из них, например [1, 2] или [3, 3].

Ограничения:

len(nums) >= 1

public class Solution
{
    public static List<int> SubsequenceSumK(List<int> nums, int k)
    {
        // {Префиксная сумма: индекс конца}
        Dictionary<int, int> prefixIndex = new Dictionary<int, int>();
        prefixIndex[0] = -1;
        int prefixSum = 0;

        for (int idx = 0; idx < nums.Count; idx++)
        {
            prefixSum += nums[idx];
            int diff = prefixSum - k;
            // Если такая префиксная сумма уже встречалась, нашли подмассив
            if (prefixIndex.ContainsKey(diff))
            {
                return new List<int> { prefixIndex[diff] + 1, idx };
            }
            prefixIndex.TryAdd(prefixSum, idx);
        }
        return new List<int> { -1, -1 };
    }
}

#include <vector>
#include <unordered_map>

using namespace std;

vector<int> subsequenceSumK(vector<int>& nums, int k) {
    // {префиксная сумма: индекс конца}
    unordered_map<int, int> prefixIndex;
    prefixIndex[0] = -1;
    int prefixSum = 0;

    for (int idx = 0; idx < nums.size(); ++idx) {
        prefixSum += nums[idx];
        int diff = prefixSum - k;
        // если такая префиксная сумма уже встречалась, нашли подмассив
        if (prefixIndex.count(diff)) {
            return {prefixIndex[diff] + 1, idx};
        }
        prefixIndex.emplace(prefixSum, idx);
    }
    return {-1, -1};
}

package main

func subsequenceSumK(nums []int, k int) []int {
    // {префиксная сумма: индекс конца}
    prefixIndex := map[int]int{0: -1}
    prefixSum := 0

    for idx, num := range nums {
        prefixSum += num
        diff := prefixSum - k
        // если такая префиксная сумма уже встречалась, нашли подмассив
        if startIdx, ok := prefixIndex[diff]; ok {
            return []int{startIdx + 1, idx}
        }
        prefixIndex[prefixSum] = idx
    }
    return []int{-1, -1}
}

import java.util.*;

public class Solution {
    public List<Integer> subsequenceSumK(List<Integer> nums, int k) {
        // {префиксная сумма: индекс конца}
        Map<Integer, Integer> prefixIndex = new HashMap<>();
        prefixIndex.put(0, -1);
        int prefixSum = 0;

        for (int idx = 0; idx < nums.size(); idx++) {
            prefixSum += nums.get(idx);
            int diff = prefixSum - k;
            // если такая префиксная сумма уже встречалась, нашли подмассив
            if (prefixIndex.containsKey(diff)) {
                return Arrays.asList(prefixIndex.get(diff) + 1, idx);
            }
            prefixIndex.putIfAbsent(prefixSum, idx);
        }
        return Arrays.asList(-1, -1);
    }
}

from typing import List

def subsequence_sum_k(nums: List[int], k: int) -> List[int]:
    # {префиксная сумма: индекс конца}
    prefix_index = {0: -1}
    prefix_sum = 0

    for idx, num in enumerate(nums):
        prefix_sum += num
        diff = prefix_sum - k
        # если такая префиксная сумма уже встречалась, нашли подмассив
        if diff in prefix_index:
            return [prefix_index[diff] + 1, idx]
        prefix_index.setdefault(prefix_sum, idx)

    return [-1, -1]

/**
 * @param {number[]} nums
 * @param {number} k
 * @returns {number[]}
 */
export function subsequenceSumK(nums, k) {
  // {префиксная сумма: индекс конца}
  const prefixIndex = {0: -1};
  let prefixSum = 0;

  for (let idx = 0; idx < nums.length; idx++) {
    prefixSum += nums[idx];
    const diff = prefixSum - k;
    // если такая префиксная сумма уже встречалась, нашли подмассив
    if (prefixIndex.hasOwnProperty(diff)) {
      return [prefixIndex[diff] + 1, idx];
    }
    prefixIndex[prefixSum] ??= idx;
  }
  return [-1, -1];
}

Оценка сложности

Время: O(n), где n - размер nums
Память: O(n), где n - количество различных префиксных сумм