523. Continuous Subarray Sum

LeetCode medium original: C# #array #csharp #hash-table #leetcode #medium #prefix-sum

Il testo del problema è tradotto dal russo per la lingua selezionata. Il codice resta invariato.

LeetCode Static

Дан intero array nums и intero k. return true, если в nums есть хорошая подarray, или false в противном случае.

Хороший подarray — это подarray, который:

имеет длину не менее двух, и

сумма elementов подarrayа является кратной k.

Учтите:

Подarray — это непрерывная часть arrayа.

intero x является кратным k, если существует intero n такое, что x = n * k. number 0 всегда является кратным k.

Esempio:

Input: nums = [23,2,4,6,7], k = 6

Output: true

Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

C# soluzione

abbinato/originale

using System.Collections.Generic;
public class Solution {
    public bool CheckSubarraySum(int[] nums, int k) {
        int prefixMod = 0;
        var modSeen = new Dictionary<int, int> { {0, -1} };
        
        for (int i = 0; i < nums.Length; i++) {
            prefixMod = (prefixMod + nums[i]) % k;
            
            if (modSeen.ContainsKey(prefixMod)) {
                if (i - modSeen[prefixMod] > 1) {
                    return true;
                }
            } else {
                modSeen[prefixMod] = i;
            }
        }
        
        return false;
    }
}

C++ soluzione

bozza automatica, rivedere prima dell'invio

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool CheckSubarraySum(vector<int>& nums, int k) {
        int prefixMod = 0;
        var modSeen = new unordered_map<int, int> { {0, -1} };
        
        for (int i = 0; i < nums.size(); i++) {
            prefixMod = (prefixMod + nums[i]) % k;
            
            if (modSeen.count(prefixMod)) {
                if (i - modSeen[prefixMod] > 1) {
                    return true;
                }
            } else {
                modSeen[prefixMod] = i;
            }
        }
        
        return false;
    }
}

Java soluzione

abbinato/originale

import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int prefixMod = 0;
        Map<Integer, Integer> modSeen = new HashMap<>();
        modSeen.put(0, -1);
        
        for (int i = 0; i < nums.length; i++) {
            prefixMod = (prefixMod + nums[i]) % k;
            
            if (modSeen.containsKey(prefixMod)) {
                if (i - modSeen.get(prefixMod) > 1) {
                    return true;
                }
            } else {
                modSeen.put(prefixMod, i);
            }
        }
        
        return false;
    }
}

JavaScript soluzione

abbinato/originale

var checkSubarraySum = function(nums, k) {
    let prefixMod = 0;
    let modSeen = new Map();
    modSeen.set(0, -1);
    
    for (let i = 0; i < nums.length; i++) {
        prefixMod = (prefixMod + nums[i]) % k;
        
        if (modSeen.has(prefixMod)) {
            if (i - modSeen.get(prefixMod) > 1) {
                return true;
            }
        } else {
            modSeen.set(prefixMod, i);
        }
    }
    
    return false;
};

Python soluzione

abbinato/originale

class Solution:
    def checkSubarraySum(self, nums, k):
        prefix_mod = 0
        mod_seen = {0: -1}

        for i in range(len(nums)):
            prefix_mod = (prefix_mod + nums[i]) % k

            if prefix_mod in mod_seen:
                if i - mod_seen[prefix_mod] > 1:
                    return True
            else:
                mod_seen[prefix_mod] = i

        return False

Go soluzione

abbinato/originale

func checkSubarraySum(nums []int, k int) bool {
    prefixMod := 0
    modSeen := map[int]int{0: -1}
    
    for i, num := range nums {
        prefixMod = (prefixMod + num) % k
        
        if prevIndex, exists := modSeen[prefixMod]; exists {
            if i - prevIndex > 1 {
                return true
            }
        } else {
            modSeen[prefixMod] = i
        }
    }
    
    return false
}

Algorithm

Инициализируйте intero prefixMod = 0 и хеш-таблицу modSeen. Инициализируйте modSeen[0] значением -1, чтобы учесть начальное значение prefixMod.

Итеративно пройдите по всем elementам arrayа nums.

Вычислите prefixMod как (prefixMod + nums[i]) % k. Если prefixMod существует в хеш-таблице: Если размер самого длинного подarrayа с модулем k составляет не менее 2, return true. Если prefixMod не существует в хеш-таблице: Установите modSeen[prefixMod] = i. Если после завершения итерации не найден хороший подarray, return false.

😎

Vacancies for this task

offerte attive with overlapping task tags are mostrati.

Tutte le offerte

Non ci sono ancora offerte attive.