하위 배열 합계는 K LeetCode 솔루션과 같습니다.

차례

문제 정책

또한 Subarray Sum Equals K LeetCode 솔루션 – "Subarray Sum Equals K"는 정수 배열 "nums"와 정수 'k'가 주어졌을 때 합계가 'k'인 연속적인 하위 배열의 총 수를 반환함을 나타냅니다.

예:

핀

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

설명 :

두 가지가있다 합이 되는 부분배열 3:

먼저 인덱스 0에서 1, 즉 [1, 2],
인덱스 2에서 2, 즉 [3]의 두 번째

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

설명 :

합이 2인 두 개의 하위 배열이 있습니다.

먼저 인덱스 0에서 1, 즉 [1, 1],
인덱스 1에서 2까지의 초, 즉 [1, 1]

접근

아이디어 :

주요 아이디어는 해시 맵을 사용하여 접두사 합계의 빈도를 저장하는 것입니다.

따라서 배열을 반복하면서 합계가 k이고 각 반복의 현재 지점에서 끝나는 하위 배열이 몇 개 있는지 찾습니다.

따라서 지금까지의 prefix sum의 값이 'prefixSum'이라면 다음 단계는 (prefixSum – k) 값을 가지는 prefix sum이 몇 개 존재하는지 확인하는 것이다. 접두사 합계의 빈도를 저장하는 해시 맵을 사용하여 O(1)에서 찾을 수 있습니다.

암호

C++ 프로그램 부분배열 합이 K와 같음:

#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 프로그램 부분배열 합이 K와 같음:

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));
    }
}

복잡성 분석 부분배열 합이 K와 같음 리트코드 솔루션

시간 복잡성

위 코드의 시간 복잡성은 O (N) 우리는 횡단하고 있기 때문에 정렬 한 번만.

공간 복잡성

위 코드의 공간 복잡성은 다음과 같습니다. O (N) 접두사 합계의 빈도를 저장하기 위해 해시 맵을 사용하고 있기 때문입니다.

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