พิมพ์ subarrays ทั้งหมดด้วยผลรวม 0


ระดับความยาก ยาก
ถามบ่อยใน อเมซอน ฟรีค่าธรรมเนียม จริง ขอบข้อมูล ไมโครซอฟท์ ห้องโอโย
แถว กัญชา

คุณได้รับอาร์เรย์จำนวนเต็มงานของคุณคือพิมพ์อาร์เรย์ย่อยที่เป็นไปได้ทั้งหมดโดย sum เท่ากับ 0 ดังนั้นเราจำเป็นต้องพิมพ์ subarrays ทั้งหมดด้วยผลรวม 0

ตัวอย่าง

พิมพ์ subarrays ทั้งหมดด้วยผลรวม 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. ค้นหาผลรวมขององค์ประกอบอาร์เรย์ที่มีตัวแปรบางตัวพูดว่า "Sum" เพื่อติดตามอาร์เรย์ย่อยที่มีผลรวม 0
  2. If รวม พบว่าเป็น 0 หมายความว่าพบอาร์เรย์ย่อยที่เป็นไปได้ตั้งแต่ 0 ถึงดัชนีปัจจุบัน
  3. ตรวจสอบว่า รวม ที่พบจากกระบวนการข้างต้นมีอยู่ในไฟล์ แผนที่ หรือไม่
  4. หากแผนที่มีผลรวมหมายความว่าเป็นผลรวมของอาร์เรย์ย่อยก่อนหน้าและตอนนี้จะกลายเป็นผลรวมขององค์ประกอบจนถึงดัชนีปัจจุบัน
  5. แทรกผลรวมปัจจุบันลงในแผนที่หากยังไม่มีอยู่

คำอธิบาย

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

เราจะสร้างแผนที่ที่มีผลรวมชั่วคราวเป็นคีย์และเวกเตอร์เป็นค่า ดังนั้นเวกเตอร์ในที่นี้แสดงถึงดัชนีที่ผลรวมขององค์ประกอบตั้งแต่เริ่มป้อนข้อมูลเท่ากับผลรวมปัจจุบัน

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

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

แต่ถ้าแผนที่มีผลรวมหมายความว่าเราพบอาร์เรย์ย่อยก่อนหน้านี้ที่มีผลรวมเดียวกัน จากนั้นเราต้องเพิ่มมูลค่าของผลรวมและดัชนีนั้น

และจากนี้เราจะแสดงรายการของเราซึ่งเราประกาศเป็นเวกเตอร์ จากนั้นถ้าค่าที่ส่งคืนมีขนาด 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” คือจำนวนองค์ประกอบในอาร์เรย์