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

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ซึ่งประกอบด้วยค่าจำนวนเต็ม n ค่า งานของเราคือ หาผลรวมของผลรวม subarray เฉพาะทั้งหมดสำหรับอาร์เรย์ที่กำหนด . ผลรวมของอาร์เรย์ย่อยคือผลรวมขององค์ประกอบของอาร์เรย์ย่อยที่กำหนด

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

Input : arr[] = {1, 2, 4}
Output : 23

คำอธิบาย −

All subarrays of the given array are :
(1), (2), (4), (1, 2), (2, 4), (1, 2, 4)
Sum of subarrays = 1 + 2 + 4 + (1+2) + (2+4) + (1+2+4) = 23

แนวทางการแก้ปัญหา

วิธีแก้ปัญหาคือการจัดเก็บผลรวม subarray แล้วจัดเรียงเพื่อค้นหาที่ไม่ซ้ำกันครั้งเดียว จากนั้นเราจะพิจารณาอาร์เรย์ย่อยที่ไม่ซ้ำกันทั้งหมดสำหรับผลรวม

อัลกอริทึม

ขั้นตอนที่ 1 − ค้นหาผลรวมของอาร์เรย์ย่อยทั้งหมดและจัดเก็บไว้ในเวกเตอร์

ขั้นตอนที่ 2 − จัดเรียงเวกเตอร์

ขั้นตอนที่ 3 - พิจารณาเวกเตอร์ทั้งหมดที่ไม่ซ้ำกันและทำเครื่องหมายผลรวมของส่วนที่เหลือเป็น 0

ขั้นตอนที่ 4 - คำนวณและพิมพ์ผลรวม

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#include <bits/stdc++.h>
using namespace std;
long int findSumOfSubArraySum(int arr[], int n){
   int i, j;
   long int sumArrayTill[n + 1] = { 0 };
   for (i = 0; i < n; i++)
      sumArrayTill[i + 1] = sumArrayTill[i] + arr[i];
   vector<long int> subArraySum;
   for (i = 1; i <= n; i++)
      for (j = i; j <= n; j++)
        subArraySum.push_back(sumArrayTill[j] - sumArrayTill[i - 1]);
   sort(subArraySum.begin(), subArraySum.end());
   for (i = 0; i < subArraySum.size() - 1; i++){
      if (subArraySum[i] == subArraySum[i + 1]) {
         j = i + 1;
         while (subArraySum[j] == subArraySum[i] && j < subArraySum.size()){
            subArraySum[j] = 0; j++;
         }
         subArraySum[i] = 0;
      }
   }
   long sum = 0;
   for (i = 0; i < subArraySum.size(); i++)
      sum += subArraySum[i];
   return sum;
}
int main(){
   int arr[] = { 1, 2, 4, 7, 9 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The sum of all unique subarray sum is "<<findSumOfSubArraySum(arr, n);
   return 0;
}

ผลลัพธ์

The sum of all unique subarray sum is 144

แนวทางอื่นโดยใช้การวนซ้ำ

อีกวิธีในการแก้ปัญหาคือการใช้ตารางแฮช เราจะค้นหาผลรวมของ subarray และเก็บไว้ในตารางแฮชและเพิ่มจำนวนแฮช จากนั้นให้หาผลรวมของอาร์เรย์ย่อยที่ไม่ซ้ำกันทั้งหมด (subarray ที่มีจำนวนแฮช 1)

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#include <bits/stdc++.h>
using namespace std;
long int findSumOfSubArraySum(int arr[], int n){
   int sumSubArraySum = 0;
   unordered_map<int, int> sumSubArray;
   for (int i = 0; i < n; i++) {
      int sum = 0;
      for (int j = i; j < n; j++) {
         sum += arr[j];
         sumSubArray[sum]++;
      }
   }
   for (auto itr : sumSubArray)
      if (itr.second == 1)
         sumSubArraySum += itr.first;
      return sumSubArraySum;
}
int main(){
   int arr[] = { 1, 2, 4, 7, 5 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The sum of all unique subarray sum is "<<findSumOfSubArraySum(arr, n);
   return 0;
}

ผลลัพธ์

The sum of all unique subarray sum is 124