ພິມໃບຍ່ອຍທັງ ໝົດ ມີ 0 ໃບ


ລະດັບຄວາມຫຍຸ້ງຍາກ Hard
ຖາມເລື້ອຍໆໃນ Amazon FreeCharge ແທ້ຈິງແລ້ວ ຂອບຂໍ້ມູນ Microsoft ຫ້ອງ OYO
Array Hash

ທ່ານໄດ້ຖືກຈັດໃຫ້ເປັນແຖວຍ່ອຍ, ວຽກງານຂອງທ່ານແມ່ນການພິມປ້າຍຍ່ອຍທີ່ເປັນໄປໄດ້ທັງ ໝົດ ດ້ວຍ ຈຳ ນວນເທົ່າກັບ 0. ດັ່ງນັ້ນພວກເຮົາ ຈຳ ເປັນຕ້ອງພິມ subarrays ທັງ ໝົດ ດ້ວຍ 0 ລວມ.

ຍົກຕົວຢ່າງ

ພິມໃບຍ່ອຍທັງ ໝົດ ມີ 0 ໃບ

arr[] = {-2, 4, -2, -1, 1, -3, 1, 5, 7, -11, -6}
Sub-Array found from 0 index to 2 index
Sub-Array found from 0 index to 4 index
Sub-Array found from 3 index to 4 index
Sub-Array found from 1 index to 6 index
Sub-Array found from 4 index to 9 index

ລະບົບວິເຄາະ

  1. ຊອກຫາຜົນລວມຂອງອົງປະກອບ array ທີ່ມີຕົວແປບາງຕົວເວົ້າວ່າ "Sum" ເພື່ອຕິດຕາມ sub-array ທີ່ມີ sum 0.
  2. If Sum ຖືກພົບວ່າເປັນ 0 ມັນ ໝາຍ ຄວາມວ່າ sub-array ທີ່ເປັນໄປໄດ້ແມ່ນພົບຈາກ 0 ຫາດັດຊະນີປັດຈຸບັນ.
  3. ກວດສອບວ່າ Sum ທີ່ພົບເຫັນຈາກຂັ້ນຕອນຂ້າງເທິງ, ແມ່ນມີຢູ່ໃນພວກເຮົາ ແຜນທີ່ ຫຼື​ບໍ່.
  4. ຖ້າແຜນທີ່ປະກອບດ້ວຍຜົນລວມ, ມັນ ໝາຍ ຄວາມວ່າມັນແມ່ນຜົນລວມທັງ ໝົດ ຂອງ sub-array ທີ່ຜ່ານມາແລະຕອນນີ້ມັນຈະກາຍເປັນຜົນລວມຂອງອົງປະກອບຈົນກ່ວາຕົວຊີ້ບອກປະຈຸບັນ.
  5. ເອົາ Sum Sum ໃສ່ແຜນທີ່ຖ້າມັນບໍ່ມີຢູ່ແລ້ວ.

ຄໍາອະທິບາຍ

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

ພວກເຮົາຈະສ້າງແຜນທີ່ທີ່ມີຜົນລວມຊົ່ວຄາວເປັນກຸນແຈແລະ vector ເປັນຄ່າ. ດັ່ງນັ້ນ, vector ຢູ່ທີ່ນີ້ສະແດງເຖິງຕົວຊີ້ບອກທີ່ຜົນລວມຂອງອົງປະກອບຕັ້ງແຕ່ເລີ່ມຕົ້ນຂອງການປ້ອນຂໍ້ມູນເທົ່າກັບຜົນລວມຂອງປັດຈຸບັນ.

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

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

ແຕ່ຖ້າແຜນທີ່ປະກອບດ້ວຍຍອດລວມມັນ ໝາຍ ຄວາມວ່າພວກເຮົາໄດ້ພົບເຫັນບັນດາສາຂາຍ່ອຍກ່ອນ ໜ້າ ນີ້ທີ່ມີຍອດລວມເທົ່າກັນ. ຈາກນັ້ນພວກເຮົາຕ້ອງເພີ່ມມູນຄ່າຂອງຜົນບວກແລະຕົວຊີ້ວັດນັ້ນ.

ແລະອອກຈາກນີ້, ພວກເຮົາສົ່ງຄືນບັນຊີລາຍຊື່ຂອງພວກເຮົາທີ່ພວກເຮົາປະກາດເປັນ vector. ຈາກບ່ອນນັ້ນຖ້າວ່າມູນຄ່າການສົ່ງຄືນມີຂະ ໜາດ 0 ມັນ ໝາຍ ຄວາມວ່າພວກເຮົາບໍ່ມີຫຍັງອີກທີ່ຜົນຜະລິດຈະຖືກພິມອອກ.

ລະຫັດ C ++ ເພື່ອພິມ subarrays ທັງ ໝົດ ດ້ວຍ 0 ລວມ

#include<iostream>
#include<unordered_map>
#include<vector>

using namespace std;
vector< pair<int, int> > getSubArray(int arr[], int n)
{
  unordered_map<int, vector<int> > Map;
  vector <pair<int, int>> result;
  int sum = 0;
  for (int i = 0; i < n; i++)
  {
    sum += arr[i];
    if (sum == 0)
      result.push_back(make_pair(0, i));
        if (Map.find(sum) != Map.end())
    {
      vector<int> vec = Map[sum];
      for (auto val = vec.begin(); val != vec.end(); val++)
        result.push_back(make_pair(*val + 1, i));
    }
    Map[sum].push_back(i);
  }
  return result;
}
void print(vector<pair<int, int>> result)
{
  for (auto j= result.begin(); j != result.end(); j++)
    cout << "Sub-Array found from " << j->first << " index to " << j->second <<" index"<< endl;
}
int main()
{
    int arr[] = {-2, 4, -2, -1, 1, -3, 1, 5, 7, -11, -6};
    int n = sizeof(arr)/sizeof(arr[0]);
  vector<pair<int, int> > result = getSubArray(arr, n);
  if (result.size() == 0)
    cout << "No such Sub-array exists";
  else
    print(result);

  return 0;
}
Sub-Array found from 0 index to 2 index
Sub-Array found from 0 index to 4 index
Sub-Array found from 3 index to 4 index
Sub-Array found from 1 index to 6 index
Sub-Array found from 4 index to 9 index

ລະຫັດ Java ເພື່ອພິມ subarrays ທັງ ໝົດ ດ້ວຍ 0 ລວມ

import java.util.*;
class Pair
{
    int start, end;
    Pair(int a, int b)
    {
        start = a;
        end = b;
    }
}
class printSubArray0Sum
{
    public static ArrayList<Pair> getSubArray(int[] arr, int n)
    {
        HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();
        ArrayList<Pair> temp = new ArrayList<>();
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            sum += arr[i];
            if (sum == 0)
                temp.add(new Pair(0, i));
            ArrayList<Integer> list = new ArrayList<>();
            if (map.containsKey(sum))
            {
                list = map.get(sum);
                for (int j = 0; j < list.size(); j++)
                {
                    temp.add(new Pair(list.get(j) + 1, i));
                }
            }
            list.add(i);
            map.put(sum, list);
        }
        return temp;
    }
    public static void print(ArrayList<Pair> result)
    {
        for (int i = 0; i < result.size(); i++)
        {
            Pair pair = result.get(i);
            System.out.println("Sub-Array found from "+ pair.start + " index to " + pair.end+" index");
        }
    }
    public static void main(String args[])
    {
        int[] arr = {-2, 4, -2, -1, 1, -3, 1, 5, 7, -11, -6};
        int n = arr.length;

        ArrayList<Pair> result = getSubArray(arr, n);
        if (result.size() == 0)
            System.out.println("No such Sub-array exists");
        else
            print(result);
    }
}
Sub-Array found from 0 index to 2 index
Sub-Array found from 0 index to 4 index
Sub-Array found from 3 index to 4 index
Sub-Array found from 1 index to 6 index
Sub-Array found from 4 index to 9 index

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ.

ຄວາມສັບສົນໃນອະວະກາດ

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ.