ค้นหาผลรวมของผลรวมอาร์เรย์ย่อยที่ไม่ซ้ำกันทั้งหมดสำหรับอาร์เรย์ที่กำหนด


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อเมซอน Facebook สีเทาOrange ตรัสรู้ ไมโครซอฟท์ นากาโร
แถว กัญชา การเรียงลำดับ

สมมติว่าคุณมีอาร์เรย์ของจำนวนเต็ม ปัญหา“ ค้นหาผลรวมของผลรวมอาร์เรย์ย่อยที่ไม่ซ้ำกันทั้งหมดสำหรับอาร์เรย์ที่กำหนด” ขอให้หาผลรวมของอาร์เรย์ย่อยที่ไม่ซ้ำกันทั้งหมด (ผลรวมของอาร์เรย์ย่อยคือผลรวมขององค์ประกอบของอาร์เรย์ย่อยแต่ละรายการ)

โดยผลรวมของอาร์เรย์ย่อยที่ไม่ซ้ำกันเราหมายถึงการบอกว่าไม่มีอาร์เรย์ย่อยที่มีค่าเท่ากัน

ตัวอย่าง

arr[] = {3, 1, 4, 5}
44
arr[] = {2,1,3,6}
36

ค้นหาผลรวมของผลรวมอาร์เรย์ย่อยที่ไม่ซ้ำกันทั้งหมดสำหรับอาร์เรย์ที่กำหนด

ขั้นตอนวิธี

  1. ประกาศก แผนที่.
  2. ชุด เอาท์พุต ไปยัง 0.
  3. สำรวจอาร์เรย์จาก i = 0 ถึง i
    1. ตั้ง รวม เพื่อ 0
    2. สำรวจอาร์เรย์จาก j = i ถึง j
      • เพิ่มค่าของ arr [j] ลงในผลรวม
      • เพิ่มผลรวมและจำนวนที่เกิดขึ้นในแผนที่
  4. สำรวจแผนที่และตรวจสอบรายการของคีย์ที่มีค่าเป็น 1
    1. เพิ่มค่าของคีย์ให้กับผลลัพธ์เมื่อใดก็ตามที่เราพบว่าเงื่อนไขนั้นพอใจ
  5. ส่งคืนเอาต์พุต

คำอธิบาย

เราได้รับไฟล์ จำนวนเต็ม แถว. งานของเราคือการหาผลรวมของอาร์เรย์ย่อยที่ไม่ซ้ำกันทั้งหมด ผลรวมของแต่ละอาร์เรย์ย่อยจะเป็นผลรวมของแต่ละองค์ประกอบของอาร์เรย์ย่อย เรากำลังจะใช้ hashing เพื่อแก้ปัญหานี้ เราจะหยิบแต่ละองค์ประกอบของอาร์เรย์เริ่มต้นผลรวมเป็น 0 เมื่อใดก็ตามที่เราเปลี่ยนค่าของ i เมื่อเราเข้าสู่วงในเราจะสำรวจอาร์เรย์จาก i ไปยัง nและเพิ่มแต่ละค่าของอาร์เรย์และผลรวม จากนั้นเราก็จัดเก็บผลรวมและจำนวนที่เกิดขึ้นในแผนที่พร้อมกัน หลังจากเยี่ยมชมอาร์เรย์ทั้งหมดแล้วให้ค้นหาผลรวมของอาร์เรย์ย่อยที่เป็นไปได้ทั้งหมด หลังจากนั้นเรามองหาผลรวมเหล่านั้นในแผนที่ซึ่งเกิดขึ้นเพียงครั้งเดียว เนื่องจากเราต้องการผลรวมของอาร์เรย์ย่อยที่ไม่ซ้ำกันซึ่งหมายความว่ามีผลรวมที่แตกต่างกัน ดังนั้นเมื่อเราพบผลรวมในแผนที่ซึ่งเกิดขึ้นครั้งเดียวหมายถึงบอกว่าความถี่ของใครคือ 1 เราจะเพิ่มและอัปเดตค่าของผลรวมเหล่านั้นลงในผลลัพธ์

พิจารณาตัวอย่างสำหรับมัน:

ตัวอย่าง

arr [] = {3, 1, 4, 5}

อันดับแรกเรามี i = 0 จากนั้นเรามี 3 เป็นองค์ประกอบและเราจะเริ่มจาก 3 เราจะเพิ่ม 3 เข้าไปในผลรวมและอัปเดต 3 ในแผนที่จากนั้นเพิ่ม 1 เข้าไปในผลรวมและอัปเดต 4 ในแผนที่ จากนั้นนำ 4 มาเป็นองค์ประกอบในผลรวมและเพิ่ม 7 เข้าไปในแผนที่ ด้วยวิธีนี้เราจะสิ้นสุดการเดินทางครั้งแรกหลังจากเยี่ยมชม 5 และอัปเดต 12 ลงในแผนที่

ดังนั้นเมื่อเราใช้ 4 เป็นองค์ประกอบและเริ่มจาก 4 เราจะอัปเดตผลรวมลงในแผนที่เนื่องจาก 4 อยู่ใน แผนที่เราจะเพิ่มความถี่ของมันและเราจะเพิกเฉยต่อผลรวมที่ความถี่ไม่ใช่ 1 ด้วยวิธีนี้เราจะสามารถจัดการกับอาร์เรย์ย่อยที่ไม่ซ้ำกันได้

รหัส

รหัส C ++ เพื่อค้นหาผลรวมของผลรวมอาร์เรย์ย่อยที่ไม่ซ้ำกันทั้งหมดสำหรับอาร์เรย์ที่กำหนด

#include<iostream>
#include<unordered_map>

using namespace std;

int findSumOfUnique(int arr[], int n)
{
    int output = 0;
    unordered_map<int, int> MAP;

    for (int i = 0; i < n; i++)
    {
        int sum = 0;
        for (int j = i; j < n; j++)
        {
            sum += arr[j];
            MAP[sum]++;
        }
    }
    for (auto entry : MAP)
        if (entry.second == 1)
            output += entry.first;

    return output;
}
int main()
{
    int arr[] = { 3, 1, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << findSumOfUnique(arr, n);
    return 0;
}
44

โค้ด Java เพื่อค้นหาผลรวมของผลรวมอาร์เรย์ย่อยที่ไม่ซ้ำกันทั้งหมดสำหรับอาร์เรย์ที่กำหนด

import java.util.HashMap;
import java.util.Map;

class SumUniqueSubArray
{
    public static int findSumOfUnique(int []arr, int n)
    {
        int output = 0;

        HashMap<Integer,Integer> MAP = new HashMap<Integer,Integer>();
        for (int i = 0; i < n; i++)
        {
            int sum = 0;
            for (int j = i; j < n; j++)
            {
                sum += arr[j];
                if (MAP.containsKey(sum))
                {
                    MAP.put(sum, MAP.get(sum) + 1);
                }
                else
                {
                    MAP.put(sum, 1);
                }
            }
        }
        for (Map.Entry<Integer,Integer> entry : MAP.entrySet())
            if (entry.getValue() == 1)
                output += entry.getKey();

        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {3, 1, 4, 5};
        int n = arr.length;
        System.out.println(findSumOfUnique(arr, n));
    }
}
44

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของเวลา

บน2ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์ เนื่องจากเราใช้ 2 ลูปซ้อนกันและการค้นหาผลรวมทำได้ใน O (1) โดยใช้ HashMap

ความซับซ้อนของอวกาศ

O (n ^ 2) ที่ไหน “ n” คือจำนวนองค์ประกอบของอาร์เรย์ เนื่องจากในกรณีที่เลวร้ายที่สุดเราอาจมีผลรวมอาร์เรย์ย่อยที่แตกต่างกัน n ^ 2