ค้นหาว่ามี subarray ที่มีผลรวม 0 หรือไม่


ระดับความยาก กลาง
ถามบ่อยใน ซิทริกซ์ เดอชอว์ แซคส์โกลด์แมน จริง MakeMyTrip ห้องโอโย Paytm TCS
แถว กัญชา

ปัญหา "ค้นหาว่ามี subarray ที่มีผลรวม 0 หรือไม่" ระบุว่าคุณได้รับไฟล์ จำนวนเต็ม แถว ประกอบด้วยจำนวนเต็มลบเช่นกัน คำสั่งปัญหาขอให้พิจารณาว่าอาร์เรย์ย่อยที่มีขนาดอย่างน้อย 1 อาร์เรย์ย่อยนี้ควรมีผลรวมเท่ากับ 1 หรือไม่

ตัวอย่าง

ค้นหาว่ามี subarray ที่มีผลรวม 0 หรือไม่

arr[] = {2,1,-3,4,5}
yes

คำอธิบาย

ที่นี่องค์ประกอบจากดัชนี 0 ถึง 2 มีผลรวม 0

arr[] = {4,1,-4,5,1}
yes

คำอธิบาย

ไม่มีอาร์เรย์ย่อยที่มีผลรวม 0

ขั้นตอนวิธี

  1. ประกาศก ชุด.
  2. เริ่มต้น รวม เพื่อ 0
  3. สำรวจอาร์เรย์ในขณะที่ ฉัน <n (ความยาวของอาร์เรย์)
    1. เพิ่มผลรวมใน arr [i] และเก็บเป็นผลรวม
    2. ตรวจสอบว่าเงื่อนไขใด ๆ ต่อไปนี้เป็นจริง:
      1. sum == 0 / arr [i] == 0 / if Set มีค่าของ sum
      2. ถ้าเป็นจริงให้คืนค่าจริง
    3. เพิ่มผลรวมในชุด
  4. ส่งคืนเท็จ

คำอธิบาย

เราได้คำสั่งปัญหาที่ขอให้ตรวจสอบว่ามีอาร์เรย์ย่อยที่มีผลรวมเท่ากับ 0 หรือไม่ในการแก้ปัญหานี้เราจะใช้ Set เพื่อแก้ปัญหานี้ เราจะจัดเก็บองค์ประกอบของอาร์เรย์ที่กำหนดไว้ในชุด จากนั้นเพิ่มค่าลงในผลรวมพร้อมกันและตรวจสอบว่ามีอาร์เรย์ย่อยที่ตรงกันกับผลรวมปัจจุบันในชุดหรือผลรวมเท่ากับ 0 หากพบว่ามีอาร์เรย์ย่อยที่มีผลรวม 0 เราจะส่งคืน จริง.

หากไม่พบอาร์เรย์ย่อยใดที่มีผลรวม 0 เราจะส่งคืนเท็จออกจากลูป นอกจากนี้ยังมีสิ่งหนึ่งหากองค์ประกอบใดเป็น 0 เราก็จะคืนค่าจริงเนื่องจากองค์ประกอบนั้นเป็นอาร์เรย์ย่อยขององค์ประกอบเดียว นั่นหมายความว่าเราพบอาร์เรย์ย่อยดังกล่าวหนึ่งรายการ

ในโค้ดเราประกาศฟังก์ชันบูลีนซึ่งจะส่งคืนจริงหรือเท็จหากพบอาร์เรย์ย่อยจะส่งคืนจริงมิฉะนั้นจะส่งคืนเท็จ

ให้เราพิจารณาตัวอย่าง:

ตัวอย่าง

arr [] = {- 3,2,1,9,6}

ในโค้ดนี้เราจะข้ามอาร์เรย์และเพิ่ม sum และ arr [i] และเก็บเป็น sum และหลังจากนั้นการตรวจสอบหาก sum == 0 หรือ arr [i] เท่ากับ 0 หรือ Set มีค่าของ sum หากเงื่อนไขใด ๆ เป็นที่พอใจเราจะคืนค่าจริงจากนั้นเพิ่มผลรวมลงใน Set

หากไม่พบอาร์เรย์ย่อยเราจะส่งคืนเท็จ

ผลรวม = 0, ตั้ง = {}

ผม = 0, arr [i] = -3

sum = sum + arr [i] => 0 + - 3 = -3

ถ้า sum == 0 หรือ arr [i] เท่ากับ 0 หรือ Set มีค่าของ sum สามค่าเป็นเท็จดังนั้นเราจะไม่ทำอะไรเลยและเพิ่ม -3 เข้าไปใน Set

ผม = 1, arr [i] = 2

sum = sum + arr [i] => -3 + 2 = -1

ถ้า sum == 0 หรือ arr [i] เท่ากับ 0 หรือ Set มีค่าของ sum สามค่าเป็นเท็จดังนั้นเราจะไม่ทำอะไรเลยและเพิ่ม -1 เข้าไปใน Set

ผม = 2, arr [i] = 1

sum = sum + arr [i] => -1 + 1 = 0

ถ้าเงื่อนไข sum == 0 เป็นที่พอใจที่นี่ดังนั้นเราจึงคืนค่าจริงหมายความว่าเราพบอาร์เรย์ย่อยที่มีผลรวม 0

เอาต์พุต: ใช่มีอาร์เรย์ย่อยที่มีผลรวม 0 อยู่

รหัส

รหัส C ++ เพื่อค้นหาว่ามี subarray ที่มีผลรวม 0 หรือไม่

#include<iostream>
#include<unordered_set>

using namespace std;

bool isSubArrayZero(int arr[], int n)
{
    unordered_set<int> Set;
    int sum = 0;
    for (int i = 0 ; i < n ; i++)
    {
        sum += arr[i];
        if (sum == 0 || Set.find(sum) != Set.end())
            return true;

        Set.insert(sum);
    }
    return false;
}
int main()
{
    int arr[] = {-3, 2, 1, 9, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    if (isSubArrayZero(arr, n))
        cout << "Yes, a sub-array with sum 0 exist";
    else
        cout << "No, a sub-array with sum 0 does not exist";
    return 0;
}
Yes, a sub-array with sum 0 exist

โค้ด Java เพื่อค้นหาว่ามี subarray ที่มีผลรวม 0 หรือไม่

import java.util.Set;
import java.util.HashSet;

class sumOfSubArrayZero
{
    public static Boolean isSubArrayZero(int arr[])
    {
        Set<Integer> set = new HashSet<Integer>();
        int Sum = 0;
        for (int i = 0; i < arr.length; i++)
        {
            Sum += arr[i];
            if (arr[i] == 0 || Sum == 0 || set.contains(Sum))
                return true;

            set.add(Sum);
        }
        return false;
    }
    public static void main(String arg[])
    {
        int arr[] = {-3, 2, 1, 9, 6};
        if (isSubArrayZero(arr))
            System.out.println("Yes, a subarray with sum 0 exists");
        else
            System.out.println("No, a subarray with sum 0 does not exist");
    }
}
Yes, a subarray with sum 0 exists

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

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

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

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

O (n) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์ เนื่องจากสามารถมีได้มากที่สุด n องค์ประกอบในชุดแฮชที่สร้างขึ้นความซับซ้อนของพื้นที่จึงเป็นเชิงเส้น