Altsətir cəmi K LeetCode Həllinə bərabərdir

Mündəricat

Problem bəyanat

The Subbarray Cəmi K LeetCode Həllinə bərabərdir - “Alt massivlərin cəmi K-yə bərabərdir” sizə “num” tam ədədlər massivi və “k” tam ədədi verildiyini bildirir, cəmi ‘k’-ə bərabər olan davamlı alt massivlərin ümumi sayını qaytarın.

Misal:

nums = [1, 2, 3],
k=3

Explanation:

İki var cəmi olan alt massivlər 3-dir:

Əvvəlcə 0-dan 1-ə qədər, yəni [1, 2],
2-dən 2-yə qədər ikinci, yəni [3]

nums = [1, 1, 1],
k=3

Explanation:

Cəmi 2 olan iki alt massiv var:

Əvvəlcə 0-dan 1-ə qədər, yəni [1, 1],
1-dən 2-yə qədər ikinci, yəni [1, 1]

Yanaşma

Idea:

Əsas ideya prefiks məbləğlərinin tezliyini saxlamaq üçün hash xəritəsindən istifadə etməkdir.

Beləliklə, biz massiv üzərində təkrarlama aparacağıq, cəmi k-yə bərabər olan və hər iterasiyanın cari nöqtəsində bitən neçə alt massiv olduğunu tapacağıq.

Beləliklə, bu nöqtəyə qədər olan prefiksin cəminin dəyəri 'prefiksCəmi' olarsa, növbəti addım dəyəri olan neçə prefiks cəminin mövcud olduğunu müəyyən etməkdir (prefiksSum – k). Onu O(1)-də prefiks məbləğlərinin tezliyini saxlayan hash xəritəsindən istifadə etməklə tapmaq olar.

Kodu

C++ Proqramı Alt xətlərin cəmi K-ə bərabərdir:

#include <bits/stdc++.h>
using namespace std;
int subarraySum(vector<int> &nums, int k)
{
    int n = nums.size();
    int answer = 0;
    unordered_map<int, int> prefixSumsFrequency;
    prefixSumsFrequency[0] = 1;
    int prefixSum = 0;
    for (int i = 0; i < n; i++)
    {
        prefixSum += nums[i];
        answer += prefixSumsFrequency[prefixSum - k];
        prefixSumsFrequency[prefixSum]++;
    }
    return answer;
}
int main()
{
    vector<int> nums = {1, 2, 3};
    int k = 3;
    cout << subarraySum(nums, k);
    return 0;
}

JAVA Proqramı Alt xətlərin cəmi K-ə bərabərdir:

import java.util.*;

public class TutorialCup {
    public static int subarraySum(int[] nums, int k) {
        int answer = 0, prefixSum = 0;
        Map<Integer, Integer> prefixSumsFrequency = new HashMap<>();
        prefixSumsFrequency.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            prefixSum += nums[i];
            answer += prefixSumsFrequency.getOrDefault(prefixSum - k, 0);
            prefixSumsFrequency.put(prefixSum, prefixSumsFrequency.getOrDefault(prefixSum, 0) + 1);
        }
        return answer;
    }

    public static void main(String[] args) {
        int[] nums = { 1, 2, 3 };
        int k = 3;
        System.out.println(subarraySum(nums, k));
    }
}

Üçün Mürəkkəblik Təhlili Alt xətlərin cəmi K-ə bərabərdir LeetCode Həlli

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (n) çünki biz yoldan keçirik array yalnız bir dəfə.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (n) çünki biz prefiks məbləğlərinin tezliyini saxlamaq üçün hash xəritəsindən istifadə edirik.

arayış https://en.wikipedia.org/wiki/Maximum_subarray_problem, https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html