325. Maximum Size Subarray Sum Equals k

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

LeetCode Static

Дан целочисленный массив nums и целое число k. Верните максимальную длину подмассива, сумма которого равна k. Если такого подмассива не существует, верните 0.

Пример

Input: nums = [1,-1,5,-2,3], k = 3

Output: 4

Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.

C# решение

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

public class Solution {
    public int MaxSubArrayLen(int[] nums, int k) {
        int prefixSum = 0;
        int longestSubarray = 0;
        Dictionary<int, int> indices = new Dictionary<int, int>();
        
        for (int i = 0; i < nums.Length; i++) {
            prefixSum += nums[i];
            
            if (prefixSum == k) {
                longestSubarray = i + 1;
            }
            if (indices.ContainsKey(prefixSum - k)) {
                longestSubarray = Math.Max(longestSubarray, i - indices[prefixSum - k]);
            }
            if (!indices.ContainsKey(prefixSum)) {
                indices[prefixSum] = i;
            }
        }
        
        return longestSubarray;
    }
}

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 int MaxSubArrayLen(vector<int>& nums, int k) {
        int prefixSum = 0;
        int longestSubarray = 0;
        unordered_map<int, int> indices = new unordered_map<int, int>();
        
        for (int i = 0; i < nums.size(); i++) {
            prefixSum += nums[i];
            
            if (prefixSum == k) {
                longestSubarray = i + 1;
            }
            if (indices.count(prefixSum - k)) {
                longestSubarray = max(longestSubarray, i - indices[prefixSum - k]);
            }
            if (!indices.count(prefixSum)) {
                indices[prefixSum] = i;
            }
        }
        
        return longestSubarray;
    }
}

Java решение

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

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

public class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        int prefixSum = 0;
        int longestSubarray = 0;
        Map<Integer, Integer> indices = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            prefixSum += nums[i];
            
            if (prefixSum == k) {
                longestSubarray = i + 1;
            }
            if (indices.containsKey(prefixSum - k)) {
                longestSubarray = Math.max(longestSubarray, i - indices.get(prefixSum - k));
            }
            if (!indices.containsKey(prefixSum)) {
                indices.put(prefixSum, i);
            }
        }
        
        return longestSubarray;
    }
}

JavaScript решение

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

var maxSubArrayLen = function(nums, k) {
    let prefixSum = 0;
    let longestSubarray = 0;
    const indices = new Map();
    
    for (let i = 0; i < nums.length; i++) {
        prefixSum += nums[i];
        
        if (prefixSum === k) {
            longestSubarray = i + 1;
        }
        if (indices.has(prefixSum - k)) {
            longestSubarray = Math.max(longestSubarray, i - indices.get(prefixSum - k));
        }
        if (!indices.has(prefixSum)) {
            indices.set(prefixSum, i);
        }
    }
    
    return longestSubarray;
};

Python решение

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

class Solution:
    def maxSubArrayLen(self, nums: List[int], k: int) -> int:
        prefixSum = 0
        longestSubarray = 0
        indices = {}
        
        for i, num in enumerate(nums):
            prefixSum += num
            
            if prefixSum == k:
                longestSubarray = i + 1
            if prefixSum - k in indices:
                longestSubarray = max(longestSubarray, i - indices[prefixSum - k])
            if prefixSum not in indices:
                indices[prefixSum] = i
        
        return longestSubarray

Go решение

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

package main

func maxSubArrayLen(nums []int, k int) int {
    prefixSum := 0
    longestSubarray := 0
    indices := make(map[int]int)
    
    for i, num := range nums {
        prefixSum += num
        
        if prefixSum == k {
            longestSubarray = i + 1
        }
        if idx, found := indices[prefixSum - k]; found {
            longestSubarray = max(longestSubarray, i - idx)
        }
        if _, found := indices[prefixSum]; !found {
            indices[prefixSum] = i
        }
    }
    
    return longestSubarray
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Algorithm

Инициализация переменных

Инициализируйте prefixSum как 0 для отслеживания префиксной суммы nums. Инициализируйте longestSubarray как 0 для отслеживания самой длинной подмассы с суммой k. Инициализируйте хеш-карту indices для хранения префиксных сумм и их индексов.

Итерация по массиву

На каждом индексе i, добавляйте nums[i] к prefixSum. Проверьте следующие условия: Если prefixSum == k, обновите longestSubarray как i + 1. Если prefixSum - k существует в indices, обновите longestSubarray, если текущая длина подмассива больше. Если текущий prefixSum еще не существует в indices, добавьте indices[prefixSum] = i.

Возврат результата

Верните значение longestSubarray.

😎

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

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

Все вакансии

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