523. Continuous Subarray Sum

LeetCode medium оригинал: C# #array #csharp #hash-table #leetcode #medium #prefix-sum

LeetCode Static

Дан целочисленный массив nums и целое число k. Верните true, если в nums есть хорошая подмассив, или false в противном случае.

Хороший подмассив — это подмассив, который:

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

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

Учтите:

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

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

Пример:

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# решение

сопоставлено/оригинал

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++ решение

auto-draft, проверить перед отправкой

#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 решение

сопоставлено/оригинал

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 решение

сопоставлено/оригинал

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 решение

сопоставлено/оригинал

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 решение

сопоставлено/оригинал

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

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

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

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

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.