ຊອກຫາວ່າມີສາຍໃຕ້ທີ່ມີ 0 ລວມ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Citrix DE Shaw Goldman Sachs ແທ້ຈິງແລ້ວ MakeMyTrip ຫ້ອງ OYO Paytm TCS
Array Hash

ບັນຫາ "ຊອກຖ້າມີ subarray ກັບ 0 ລວມກັນ" ລະບຸວ່າທ່ານໄດ້ຖືກມອບໃຫ້ integer array ບັນຈຸເລກເຕັມທາງລົບເຊັ່ນກັນ. ຄຳ ຖະແຫຼງກ່ຽວກັບບັນຫາຂໍໃຫ້ ກຳ ນົດວ່າຂະ ໜາດ ຍ່ອຍໃດ ໜຶ່ງ ຂອງຂະ ໜາດ ຢ່າງ ໜ້ອຍ ສຸດ 1. ແຖວຍ່ອຍນີ້ຄວນມີຜົນບວກເທົ່າກັບ 1.

ຍົກຕົວຢ່າງ

ຊອກຫາວ່າມີສາຍໃຕ້ທີ່ມີ 0 ລວມ

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

ຄໍາອະທິບາຍ

ນີ້, ອົງປະກອບຈາກດັດຊະນີ 0 ເຖິງ 2 ມີຜົນບວກ 0.

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

ຄໍາອະທິບາຍ

ບໍ່ມີແຖວຍ່ອຍທີ່ມີຜົນລວມ 0.

ລະບົບວິເຄາະ

  1. ປະກາດກ ທີ່ກໍານົດໄວ້.
  2. ເລີ່ມຕົ້ນ sum to 0
  3. Traverse ຂບວນການ, ໃນຂະນະທີ່ i <n (ຄວາມຍາວຂອງຂບວນ).
    1. ເພີ່ມຍອດເຂົ້າມາທີ່ [i] ແລະເກັບມ້ຽນມັນເພື່ອເປັນຜົນລວມ.
    2. ກວດເບິ່ງວ່າມີເງື່ອນໄຂໃດ ໜຶ່ງ ຕໍ່ໄປນີ້ແມ່ນບໍ່:
      1. sum == 0 / ມາຮອດ [i] == 0 / ຖ້າຊຸດບັນຈຸມີຄ່າຂອງຜົນລວມ.
      2. ຖ້າຫາກວ່າເປັນຄວາມຈິງ, ຫຼັງຈາກນັ້ນກັບຄືນມາເປັນຄວາມຈິງ.
    3. ເພີ່ມຍອດເຂົ້າໃນຊຸດ.
  4. ສົ່ງຄືນທີ່ບໍ່ຖືກຕ້ອງ.

ຄໍາອະທິບາຍ

ພວກເຮົາໄດ້ຮັບ ຄຳ ຖະແຫຼງທີ່ມີບັນຫາທີ່ຂໍໃຫ້ຄົ້ນພົບວ່າມີອະນຸສັນຍາໃດໆທີ່ມີຜົນບວກເທົ່າກັບ 0. ເພື່ອແກ້ໄຂບັນຫານີ້ພວກເຮົາຈະໃຊ້ຊຸດເພື່ອແກ້ໄຂບັນຫານີ້. ພວກເຮົາ ກຳ ລັງຈະເກັບສ່ວນປະກອບຂອງອາເລທີ່ໃຫ້ໄວ້ໃນຊຸດ. ຫຼັງຈາກນັ້ນພ້ອມກັນເພີ່ມມູນຄ່າເຂົ້າໃນຜົນລວມແລະກວດເບິ່ງວ່າມີການຈັບຄູ່ກັບ ຄຳ ສັ່ງຍ່ອຍທີ່ມີຜົນບວກປະຈຸບັນຢູ່ໃນຊຸດຫລືລວມຕົວມັນເອງເທົ່າກັບ 0. ຖ້າພົບວ່າມີຂອດຍ່ອຍທີ່ມີຜົນບວກ 0 ແລ້ວພວກເຮົາຈະກັບຄືນ ຄວາມຈິງ.

ຖ້າບໍ່ມີອານຸສາວະລີຍ່ອຍໃດໆພົບວ່າມີຜົນລວມ 0, ຫຼັງຈາກນັ້ນພວກເຮົາ ກຳ ລັງຈະກັບຄືນ ຄຳ ທີ່ບໍ່ຖືກຕ້ອງອອກຈາກວົງຈອນ. ອີກຢ່າງ ໜຶ່ງ, ມັນມີສິ່ງ ໜຶ່ງ, ຖ້າວ່າມີອົງປະກອບໃດ ໜຶ່ງ ແມ່ນ 0 ແລ້ວພວກເຮົາກໍ່ຈະກັບມາເປັນຄວາມຈິງເພາະວ່າອົງປະກອບຕົວມັນເອງແມ່ນອະນຸພາກຂອງອົງປະກອບດຽວ. ສະນັ້ນມັນ ໝາຍ ຄວາມວ່າພວກເຮົາພົບເຫັນ ໜຶ່ງ ຂອດຍ່ອຍດັ່ງກ່າວ.

ໃນລະຫັດນີ້, ພວກເຮົາປະກາດຟັງຊັນ Boolean, ມັນຈະກັບຄືນມາທັງຄວາມຈິງຫຼືຜິດ, ຖ້າພົບເຫັນແຖວຍ່ອຍມັນຈະກັບມາເປັນຄວາມຈິງ, ຖ້າບໍ່ດັ່ງນັ້ນມັນກໍ່ຈະກັບຄືນມາປອມ.

ຂໍໃຫ້ເຮົາພິຈາລະນາຕົວຢ່າງ:

ຍົກຕົວຢ່າງ

ມາຮອດ [] = {- 3,2,1,9,6}

ໃນລະຫັດນີ້, ພວກເຮົາຈະ ກຳ ລັງລອກແຖວແລະເພີ່ມ sum ແລະມາຮອດ [i] ແລະເກັບເຂົ້າໄປໃນຜົນລວມແລະຫຼັງຈາກນັ້ນກວດເບິ່ງ, ຖ້າຜົນບວກ == 0 ຫຼືມາຮອດ [i] ເທົ່າກັບ 0 ຫຼືຊຸດທີ່ມີຄ່າຂອງຜົນລວມ, ຖ້າມີເງື່ອນໄຂໃດ ໜຶ່ງ ທີ່ພວກເຮົາພໍໃຈແລ້ວພວກເຮົາກໍ່ຈະກັບມາເປັນຄວາມຈິງແລະຫຼັງຈາກນັ້ນເພີ່ມຜົນລວມເຂົ້າໃນການຕັ້ງຄ່າ.

ຖ້າຫາກວ່າບໍ່ມີແຖວຍ່ອຍໃດໆທີ່ພົບເຫັນແລ້ວພວກເຮົາຈະກັບຄືນມາປອມ.

ຜົນບວກ = 0, ຕັ້ງຄ່າ = {}

i = 0, ມາຮອດ [i] = -3

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

ຖ້າຜົນລວມ == 0 ຫລືມາຮອດ [i] ເທົ່າກັບ 0 ຫລືຊຸດມີຄ່າຂອງຜົນລວມ, ສາມໃນນັ້ນບໍ່ຖືກຕ້ອງ, ສະນັ້ນພວກເຮົາບໍ່ເຮັດຫຍັງຢູ່ບ່ອນນີ້ແລະຕື່ມ -3 ເຂົ້າໃນຊຸດ.

i = 1, ມາຮອດ [i] = 2

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

ຖ້າຜົນລວມ == 0 ຫລືມາຮອດ [i] ເທົ່າກັບ 0 ຫລືຊຸດມີຄ່າຂອງຜົນລວມ, ສາມໃນນັ້ນບໍ່ຖືກຕ້ອງ, ສະນັ້ນພວກເຮົາບໍ່ເຮັດຫຍັງຢູ່ບ່ອນນີ້ແລະຕື່ມ -1 ເຂົ້າໃນຊຸດ.

i = 2, ມາຮອດ [i] = 1

ຜົນບວກ = ຜົນບວກ + ມາຮອດ [i] => -1 + 1 = 0

ຖ້າຜົນລວມ == 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" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ເນື່ອງຈາກວ່າມັນສາມາດມີຫຼາຍທີ່ສຸດໃນອົງປະກອບໃນຊຸດ hash ທີ່ຖືກສ້າງຂື້ນ, ຄວາມສັບສົນຂອງພື້ນທີ່ແມ່ນເປັນເສັ້ນ.