523. Continuous Subarray Sum

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

선택한 UI 언어에 맞게 문제 텍스트를 러시아어에서 번역합니다. 코드는 변경하지 않습니다.

LeetCode Static

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

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

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

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

Учтите:

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

정수 x является кратным k, если существует 정수 n такое, что x = n * k. number 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++ 해법

자동 초안, 제출 전 검토

#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.

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

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

😎

Vacancies for this task

활성 채용 with overlapping task tags are 표시됨.

전체 채용

아직 활성 채용이 없습니다.