주어진 합계가있는 부분 배열

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

문제 정책

주어진 합계 문제가있는 부분 배열에서 우리는 정렬 n 개의 긍정적 인 요소를 포함합니다. 우리는 subarray의 모든 요소의 합이 given_sum과 같은 subarray를 찾아야합니다. 하위 배열은 배열의 시작 또는 끝에서 일부 요소를 삭제하여 원래 배열에서 가져옵니다.

예

ㅏ. 입력 배열 : [1, 3, 7, 9, 11, 15, 8, 6]

합계 = 19
출력은 다음과 같습니다. 1 및 3 → [3, 7, 9], 부분 배열 합계 = 19

비. 입력 배열 : [1, 3, 7, 9, 11, 15, 8, 6]

합계 = 20
출력은 다음과 같습니다. 0 및 3 → [1, 3, 7, 9], 부분 배열 합계 = 20

씨. 입력 배열 : [1, 3, 7, 9, 11, 15, 8, 6]

합계 = 40
출력은 다음과 같습니다. 주어진 합계가있는 하위 배열이 없습니다.

디. 입력 배열 : [4, 3, 2, 8, 9, 11]

합계 = 8
출력은 다음과 같습니다. 3 및 3 → [8], 부분 배열 합계 = 8

접근법 1

암호알고리즘

모든 하위 배열을 고려하고 모든 하위 배열의 합계를 확인합니다.

1. 두 개의 루프를 실행하십시오.
2. 외부 루프는 시작 인덱스를 그림으로 표시합니다.
3. 내부 루프는 모든 하위 배열을 찾고 합계를 찾습니다.
4. sum = current_sum 인 경우 current_sum은 현재 하위 배열, 인쇄 시작 및 끝 인덱스의 합계입니다.

실시

주어진 합계를 사용하는 하위 배열을위한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
int SubarraySum(int array[], int N, int sum)
{
    int current_sum, i, j;
    //i is start point and j - 1 is end point
    for (i = 0; i < N; i++)
    {
        current_sum = array[i];
        for (j = i+1; j < N + 1; j++)
        {
            if (current_sum == sum)
            {
                cout<<"Subarray with given sum is between indexes "<<i<<" and "<<j-1<<endl; 
                return 1;
            }
            else if (current_sum > sum)
            {
                break;
            }
           current_sum = current_sum + array[j];
        }
    }
    cout<<"No subarray found with given sum"<<endl;
    return 0;
}
 
//Main function
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int sum;
    cin>>sum;
    SubarraySum(a,n,sum);
    return 0;
}

import java.util.Scanner;
class sum
{
    public static int SubarraySum(int array[], int N, int sum)
    {
        int current_sum, i, j;
        //i is start point and j - 1 is end point
        for (i = 0; i < N; i++)
        {
            current_sum = array[i];
            for (j = i+1; j < N + 1; j++)
            {
                if (current_sum == sum)
                {
                    System.out.println("Subarray with given sum is between indexes " + i + " and " + (j-1)); 
                    return 1;
                }
                else if (current_sum > sum)
                {
                    break;
                }
               current_sum = current_sum + array[j];
            }
        }
        System.out.println("No subarray found with given sum");
        return 0;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int sum;
        sum = sr.nextInt();
        SubarraySum(a,n,sum);
    }
}

8
1 3 8 9 11 13 17 21
28

Subarray with given sum is between indexes 2 and 4

접근법 2

암호알고리즘

부분 배열 합계 만들기 기능 배열과 합계를 인수로 취하고 주어진 합계로 하위 배열의 시작 및 끝 인덱스를 제공합니다.

1. 먼저 current_sum을 배열의 첫 번째 요소로 초기화하고 시작 인덱스를 0으로 저장합니다.
2. current_sum이 합계를 초과하면 시작 요소를 제거하고 시작 인덱스를 증가시킵니다.
3. current_sum이 sum과 같으면 시작 및 끝 인덱스를 반환합니다.
4. current_sum에 하나씩 요소를 추가합니다.
5. 루프가 끝나면 "No subarray found with given_sum"을 인쇄합니다.

주어진 합계를 사용하는 부분 배열 구현

C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
int SubarrySum(int array[], int n, int sum)
{
    //Initialize current_sum = first element.Therefore, start_index =0
    int current_sum = array[0];
    int start_index = 0;
    
    //if current_sum > sum remove last element
    for(int i = 1; i <= n; i++)
    {
        while(current_sum > sum && start_index < i-1)
        {
            current_sum = current_sum - array[start_index];
            start_index++;
        }
        if(current_sum == sum)
        {
            cout<<"Subarray with given sum is between indexes "<<start_index<<" and "<<i-1<<endl;
            return 1;
        }
        //Add current element to current_sum
        if(i < n)
        {
          current_sum = current_sum + array[i];
        }
    }
    cout<<"No subarray found with given sum"<<endl;
    return 0;
}
 
//Main function
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int sum;
    cin>>sum;
    SubarrySum(a,n,sum);
    return 0;
}

import java.util.Scanner;
class sum
{
    public static int SubarraySum(int array[], int n, int sum)
    {
            //Initialize current_sum = first element.Therefore, start_index =0
        int current_sum = array[0];
        int start_index = 0;

        //if current_sum > sum remove last element
        for(int i = 1; i <= n; i++)
        {
            while(current_sum > sum && start_index < i-1)
            {
                current_sum = current_sum - array[start_index];
                start_index++;
            }
            if(current_sum == sum)
            {
                System.out.println("Subarray with given sum is between indexes " + start_index + " and " + (i-1)); 
                return 1;
            }
            //Add current element to current_sum
            if(i < n)
            {
              current_sum = current_sum + array[i];
            }
        }
        System.out.println("No subarray found with given sum");
        return 0;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int sum;
        sum = sr.nextInt();
        SubarraySum(a,n,sum);
    }
}

6
10 6 8 4 3 8
34

No subarray found with given sum