查找具有給定總和的子數組(處理負數)


難度級別
經常問 亞馬遜 優惠券 德里韋里 GE醫療集團 信息邊緣 月蛙實驗室
排列 哈希 滑動窗口

問題“查找具有給定總和的子數組(處理負數)”表示給您一個 整數 排列,也包含負整數和一個稱為“ sum”的數字。 問題陳述要求打印子陣列,該子陣列總計為一個稱為“ sum”的給定數字。 如果有多個子數組作為我們的輸出,請打印其中的任何一個。

查找具有給定總和的子數組(處理負數)

arr[] = {2,4,-2,3,1}
sum = 1
Sum found between index 2 to index 3
arr[] = {12,10,-20,30,1}
sum = 20
Sum found between index 1 to index 3
arr[] = {2,4,-2,3,1}
sum = -1
No such sub-array exists.

算法

  1. 聲明一個 地圖.
  2. 在你的生活中 當前總和 到0。
  3. 遍歷數組, 當我<n,
    1. 總結currentSum和數組元素的值,並將其存儲到currentSum。
    2. 檢查currentSum是否等於和。
      • 如果為true,則將索引打印為0到i併中斷。
    3. 檢查地圖是否包含值currentSum-sum。
      • 如果為true,則將索引作為地圖的currentSum值打印到i併中斷。
    4. 如果任何給定條件都不滿足,則意味著在給定總和下我們什麼也沒找到。

解釋

我們給出了一個問題陳述,要求找出總計為給定總和的子數組,如果找到多個子數組,則打印其中的任何一個。 我們將要使用 哈希圖 我們將存儲 當前總和 及其索引(如果將的每個元素相加後沒有一個條件滿足) 排列 和currentSum(之前已初始化為0)。

讓我們考慮一個例子:

arr [] = {14,1,-10,20,1},sum = 5

我們給出了一個整數數組,其中還包含一些負整數和一個數字和。 我們必須找出子數組,它們加起來等於給定的數字和。 在遍歷整個數組時,我們應該保持currentSum,這就是給我們可能的子數組。

i = 0,currentSum = 0

currentSum = currentSum + arr [i] => currentSum = 14,現在我們的currentSum中有14,我們將檢查它是否等於給定的和5,並且該結果為false,然後我們將檢查map是否包含表示14-5 = 9的currentSum-sum也是錯誤的。 因此,我們將討論下一個元素。 因此,我們將currentSum和i添加到地圖中。

i = 1,currentSum = 14

currentSum = currentSum + arr [i] => 14 + 1 = 15,currentSum = 15,現在我們的currentSum中有15,我們將檢查它是否等於給定的總和,但不滿足,如果映射包含15-5-10的currentSum-sum也是錯誤的。 因此,我們將currentSum和i添加到地圖中。

i = 2,currentSum = 15,

currentSum = currentSum + arr [i] => 15 +(-10),currentSum = 5,現在我們的currentSum中有15,我們將檢查它是否等於給定的總和,即5,我們發現條件滿足,意味著我們得到了輸出,然後將子數組0的索引打印到i。

推薦碼

C ++代碼查找具有給定總和的子數組(處理負數)

#include<iostream>
#include<unordered_map>

using namespace std;

void getSubArray(int arr[], int n, int sum)
{
    unordered_map<int, int> map;
    int currentSum = 0;
    for (int i = 0; i < n; i++)
    {
        currentSum = currentSum + arr[i];
        if (currentSum == sum)
        {
            cout << "Sum found between index "<< 0 << " to index " << i << endl;
            return;
        }
        if (map.find(currentSum - sum) != map.end())
        {
            cout << "Sum found between index "<< map[currentSum - sum] + 1 << " to index " << i << endl;
            return;
        }
        map[currentSum] = i;
    }
    cout << " No such sub-array exists ";
}
int main()
{
    int arr[] = {14, 1, -10, 20, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    int sum = 5;
    getSubArray(arr, n, sum);
    return 0;
}
Sum found between index 0 to index 2

Java代碼查找具有給定總和的子數組(處理負數)

import java.util.HashMap;

class printSubArraywithGivenSum
{
    public static void getSubArray(int[] arr, int n, int sum)
    {
        int currentSum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < n; i++)
        {
            currentSum = currentSum + arr[i];
            if (currentSum - sum == 0)
            {
                System.out.println("Sum found between index "+ 0 + " to index " + i);
                return;
            }
            if (map.containsKey(currentSum - sum))
            {
                int val=map.get(currentSum-sum)+1;
                System.out.println("Sum found between index "+ val+" to index " + i);
                return;
            }
            map.put(currentSum, i);
        }
        System.out.println("No such sub-array exists");
    }
    public static void main(String[] args)
    {
        int[] arr = {14, 1, -10, -20, 2};
        int n = arr.length;
        int sum = 5;
        getSubArray(arr, n, sum);
    }
}
Sum found between index 0 to index 2

複雜度分析

時間複雜度

上) 哪裡 “ N” 是數組中元素的數量。

空間複雜度

上) 哪裡 “ N” 是數組中元素的數量。