합계를 K로 나눌 수있는 쌍으로 배열 나누기

난이도 쉽게
자주 묻는 질문 아마존 Microsoft
배열 해시조회수 25

합을 K로 나눌 수있는 쌍으로 배열을 나누는 것은 때때로 다양한 조정과의 인터뷰에서 요구되는 문제입니다. 나를 아는 사람들은 이러한 문제를 이야기로 바꾸는 습관을 알고 있습니다. 이 기사에서는이 문제를 살펴 보겠습니다.

문제를 이해하기위한 상황

전염병이 확산됨에 따라 우리는 가난한 사람들에게 도움과 구호를 제공하기 위해 많은 조직을 추진하고 있습니다. 오늘 우리는 이러한 구호 활동의 조정자입니다. 우리는 배급 자루를 모아서“k”자루로 나누는 임무를 맡았습니다. 우리가 각 가정에서받는 식량은 배열로 표시됩니다. 더 나은 이해를 위해. 더 명확하게하기 위해 샘플 테스트 케이스를 살펴 보겠습니다.

입력:

5

A = [4,5,0, -2, -3,1]

출력:

7

5로 나눌 수있는 부분 배열의 수는 다음과 같습니다.

[4,5,0,-2,-3,1],[5],[5,0],[5,0,-2,-3],[0],[0,-2,-3],[-2,-3]

배열은 각 가정에서받은 패킷 수를 나타냅니다. 우리는 가장 가까운 위치에 k 개의 패킷을 전달하기 위해 인접한 가정을 모으고 있습니다. 더 쉽게, 우리는 배열을 하위 배열로 나누는 방법을 찾고 있습니다. 문제를 해결하는 다양한 방법을 고려할 수 있습니다. 그러나이 게시물에서는 매우 이해하기 쉬운 가장 쉬운 방법을 제시합니다.

합계를 K로 나눌 수있는 쌍으로 배열을 나누는 알고리즘

  • 우리는 상기 인덱스까지 합계를 보유하는 배열을 생성 할 것입니다.
  • 그런 다음 합계를 인덱스로 나눌 때이 인덱스까지 찾은 나머지를 찾습니다.
  • 나머지가 0보다 작 으면 k를 더합니다.
  • Hashmap은 나머지와 그 발생을 키-값 쌍으로 저장합니다.
  • 그런 다음 나머지를 사용하여 생성 할 수있는 하위 집합의 수를 찾습니다.
  • Sum = Sum + 값 * (값 -1) / 2

과정을 보여주는 그림은

합계를 K로 나눌 수있는 쌍으로 배열 나누기
설명 된 문제

이제 수행 할 작업을 수행하는 방법을 파악 했으므로 코드를 살펴 보겠습니다.

자바 코드

class Solution 
{
    public int subarraysDivByK(int[] A, int k) 
    {
        if(A==null || A.length<1)
            return -1;
        int sum[]=new int[A.length+1];
        for(int i=1;i<sum.length;i++)
        {
            sum[i]=sum[i-1]+A[i-1];
        }
        HashMap<Integer,Integer>combos=new HashMap<Integer,Integer>();
        for(int i=0;i<sum.length;i++)
        {
            int cur=sum[i]%k;
            if(cur<0)
                cur=cur+k;
            if(!combos.containsKey(cur))
                combos.put(cur,1);
            else
                combos.put(cur,combos.get(cur)+1);
        }
        System.out.println(combos);
        int ans=0;
        for(int i:combos.values())
        {
            ans+=i*(i-1)/2;
        }
        return ans;
    }
}

C ++ 코드

class Solution 
{
public:
    int subarraysDivByK(vector<int>& A, int k) 
    {
     if(A.size()<1)
            return -1;
        int sum[A.size()+1];
        for(int i=1;i<A.size()+1;i++)
        {
            sum[i]=sum[i-1]+A[i-1];
        }
        unordered_map<int,int>combos;
        for(int i=0;i<A.size()+1;i++)
        {
            int cur=sum[i]%k;
            if(cur<0)
                cur=cur+k;
            combos[cur]+=1;
        }
        int ans=0;
        for(auto i:combos)
        {
            ans+=(i.second)*(i.second-1)/2;
        }
        return ans;    
    }
};
5
{4, 5, 0, -2, -3, 1}
7

K로 나눌 수있는 합계를 사용하여 배열을 쌍으로 나누기위한 복잡성 분석

이 솔루션에서 문제의 시간 복잡성 및 공간 복잡성은 다음과 같이 나열 될 수 있습니다.

시간 복잡성 = O (n)

공간 복잡성 = O (n)

어떻게?

첫째, 공간 복잡성

  • N 개의 항목으로 구성된 HashMap에는 모든 값이 있습니다.
  • 이지도는 우리가 가지고있는 나머지 수만큼 큽니다
  • 결론적으로, 이것은 공간 복잡성을 O (n)로 이끌고 있습니다.

둘째, 시간 복잡성

  • 솔루션에서 세 개의 루프를 실행하고 있습니다.
  • 첫째, sum = O (n)을 찾는 루프
  • 둘째, 나머지를 찾는 루프 = O (n)
  • 셋째, 모든 조합 = O (나머지) 찾기
  • 결론적으로,이 모든 것이 O (n)의 시간 복잡도로 이어집니다.

참조

Translate »