ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด n ซึ่งประกอบด้วยค่าจำนวนเต็ม งานของเราคือ ค้นหาว่ามี subarray ที่มีผลรวมเป็น 0 หรือไม่
เราจำเป็นต้องตรวจสอบว่าอาร์เรย์ที่ระบุมีอาร์เรย์ย่อยที่ผลรวมขององค์ประกอบทั้งหมดเท่ากับ 0 หรือไม่
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล: arr[] ={3, 1, -2, 1, 4, 5}
ผลลัพธ์: ใช่
คำอธิบาย:
Subarray {1, -2, 1} มีผลรวมของค่าทั้งหมดเท่ากับ 0
แนวทางแก้ไข:
วิธีแก้ปัญหาอย่างง่ายโดยพิจารณาจากอาร์เรย์ย่อยทั้งหมดและตรวจสอบผลรวมขององค์ประกอบทั้งหมดเท่ากับ 0
วิธีแก้ไขปัญหาอื่นคือการใช้ hashing เราจำเป็นต้องวนรอบอาร์เรย์แล้วหาผลรวมจนถึงดัชนีปัจจุบันและเก็บไว้ในตารางแฮช
จากนั้นตรวจสอบในตารางแฮช หากค่าผลรวมเท่ากับที่พบในอาร์เรย์ย่อยที่มีผลรวม =0 ก่อนหน้านี้
หากพบ subarray ให้คืนค่า True
มิฉะนั้นส่งคืน เท็จ
โปรแกรมแสดงการทำงานของปัญหาของเรา
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
bool isSubArraySumZero(int arr[], int n) {
unordered_set<int> sumHash;
int currSum = 0;
for (int i = 0 ; i < n ; i++) {
currSum += arr[i];
if (currSum == 0 || sumHash.find(currSum) != sumHash.end())
return true;
sumHash.insert(currSum);
}
return false;
}
int main() {
int arr[] = { 3, 1, -2, 1, 4, 5 };
int n = sizeof(arr)/sizeof(arr[0]);
if (isSubArraySumZero(arr, n))
cout<<"SubArray with sum equal to 0 exists in the array";
else
cout<<"No subarray exists";
return 0;
} ผลลัพธ์
SubArray with sum equal to 0 exists in the array
