Совокупная сумма для поиска подмассивов, сумма которых равна заданному значению

Я пытаюсь понять логику следующего кода, однако я не совсем понимаю две части кода, потому что математика, поддерживающая логику, мне не совсем ясна в данный момент.

  1. ЗАБЛУЖДЕНИЕ 1: я не понимаю, зачем нам ставить 0 с числом = 1 на карту, прежде чем мы начнем находить сумму массива? Как это помогает?

  2. ЗАБЛУЖДЕНИЕ 2: если я передвину map.put(sum, map.getOrDefault(sum)+1) после условия if(), я получу правильное решение. Однако, если я помещу его в место, как показано в коде ниже, это даст мне неверный результат. Вопрос в том, почему позиция this имеет значение, когда мы ищем значение sum-k на карте для нахождения количества

    public int subarraySum(int[] nums, int k) {

     HashMap<Integer,Integer> prefixSumMap = new HashMap<>();
     prefixSumMap.put(0, 1); // CONFUSION 1

     int sum = 0;
     int count = 0;

     for(int i=0; i<nums.length; i++) {
         sum += nums[i];

         prefixSumMap.put(sum, prefixSumMap.getOrDefault(sum, 0)+1); //CONFUSION 2
         if(prefixSumMap.containsKey(sum - k)) {
             count += prefixSumMap.get(sum - k);
         }
     }

     return count;
 }

java hashmap math prefix-sum
person Umer Farooq    schedule 21.09.2020    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Вы можете найти это интересным. Я изменил метод, чтобы использовать длинные числа, чтобы предотвратить целочисленное переполнение, приводящее к отрицательным числам.

Оба эти метода прекрасно работают для положительных чисел. Несмотря на то, что первый намного проще, оба они возвращают одно и то же значение для тестового массива.

public static void main(String[] args) {
Random r = new Random();
long[] vals = r.longs(10_000_000, 1, 1000).toArray();
long k = 29329;
System.out.println(positiveValues(vals, k));
System.out.println(anyValues(vals, k));


public static int positiveValues(long[] array, long k) {
    
    Map<Long,Long> map = new HashMap<>(Map.of(0L,1L));
    int count = 0;
    long sum = 0;
    
    for (long v : array) {
      sum += v;
      map.put(sum,1L);
       if (map.containsKey(sum-k)) {
           count++;
       }
    }
    return count;
}

public static int anyValues(long[] nums, long k) {

     HashMap<Long,Long> prefixSumMap = new HashMap<>();
     prefixSumMap.put(0L, 1L); 

     long sum = 0;
     int count = 0;

     for(int i=0; i<nums.length; i++) {
         sum += nums[i];
         prefixSumMap.put(sum, prefixSumMap.getOrDefault(sum, 0L)+1L);
         if(prefixSumMap.containsKey(sum - k)) {
             count += prefixSumMap.get(sum - k);
         }
     }
     return count;
 }

Кроме того, заявление

    long v = prefixSumMap.getOrDefault(sum,  0L) + 1L;

Всегда возвращает 1 для положительных массивов. Это связано с тем, что предыдущие суммы никогда не могут встречаться повторно только для положительных значений.

Этот оператор, а также тот, который вычисляет count, беря значение из карты, позволяет массиву содержать как положительные, так и отрицательные числа. То же самое верно для -k и всех положительных значений.

Для следующего ввода:

long[] vals = {1,2,3,-3,0,3};

Подмассивы, сумма которых равна 3,

(1+2), (3), (1+2+3-3), (1+2+3-3+0), (3-3+0+3), (0+3), (3)

Поскольку добавление отрицательных чисел может привести к предыдущим суммам, их необходимо учитывать. Решение для положительных значений этого не делает.

Это также будет работать для всех отрицательных значений. Если k положительное, будет найден подмассив no, так как все суммы будут отрицательными. Если k отрицательно, возможно, будут найдены один или несколько подмассивов may.

person WJS    schedule 22.09.2020

arrow_upward
0
arrow_downward

#1: put(0, 1) — это удобно, поэтому вам не нужно иметь дополнительный оператор if, проверяющий, соответствует ли sum == k.

Скажем k = 6, и у вас есть ввод [1,2,3,4], затем, после того как вы обработали 3, у вас есть sum = 6, что, конечно, означает, что подмассив [1, 2, 3] необходимо подсчитать. Поскольку sum - k равно 0, get(sum - k) возвращает 1 для добавления к count, что означает, что нам не нужен отдельный if (sum == k) { count++; }.

#2: prefixSumMap.put(sum, prefixSumMap.getOrDefault(sum, 0)+1) означает, что при первом просмотре суммы выполняется put(sum, 1). Во второй раз оно становится put(sum, 2), в третий раз put(sum, 3) и так далее.

По сути, карта представляет собой карту суммы на количество просмотров этой суммы.

Например. если k = 3 и ввод равен [0, 0, 1, 2, 4], к тому времени, когда 2 будет обработано, sum = 3 и карта содержит { 0=3, 1=1, 3=1 }, поэтому get(sum - k), также известный как get(0), возвращает 3, потому что есть 3 подмассива, суммирующиеся с 3: [0, 0, 1, 2], [0, 1, 2] и [1, 2]

Аналогично, если k = 4 и ввод равен [1, 2, 0, 0, 4], к тому времени, когда 4 будет обработано, sum = 7 и карта содержит { 0=1, 1=1, 3=3, 7=1 }, поэтому get(sum - k), также известный как get(3), возвращает 3, потому что есть 3 подмассива, суммирующиеся с 3: [0, 0, 4], [0, 4] и [4].

Примечание. Все это предполагает, что значения не могут быть отрицательными.

person Andreas    schedule 21.09.2020