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


자주 묻는 질문 아마존 블룸버그 게시물에서 ByteDance Expedia Facebook 구글 링크드인 신탁 페이팔 Quora Snapchat 테슬라 Twilio 비자, 월마트 연구소 Yandex 주차
리트코드 LeetCodeSolutions Tik의 톡조회수 90

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

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

예:

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

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

설명 :

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

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

설명 :

합이 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;
}
2

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

복잡성 분석 부분배열 합이 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

균열 시스템 설계 인터뷰
Translate »
2