Hər biri Hədəf Cəmi LeetCode Həlli olan iki üst-üstə düşməyən alt massiv tapın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic google microsoftBaxılıb 38

Problem bəyanat

The Hər biri Hədəf Cəmi LeetCode Həlli olan iki üst-üstə düşməyən alt massiv tapın – “Hər biri Hədəf məbləği olan iki üst-üstə düşməyən alt massiv tapın” sizə tam ədəd verildiyini bildirir nömrə və tam ədəd hədəf, burada vəzifə massiv nömrələrindən üst-üstə düşməyən iki alt massiv tapmaqdır ki, alt massivin elementlərinin cəmi hədəfə bərabər olsun. Bir neçə cavab ola bilər, ona görə də iki alt massivin uzunluqlarının cəminin olduğu cavabı tapmalısınız. minimum.

Çıxış olmalıdır uzunluqların minimum cəmi tələb olunan iki alt massivdən və ya belə iki alt massivi tapa bilmirsinizsə -1 qaytarın.Hər biri Hədəf Cəmi LeetCode Həlli olan iki üst-üstə düşməyən alt massiv tapınPin

Misal:

Daxiletmə: ədədlər: { 5, 2, 9, 7, 8, 2} hədəf : 7

Çıxış: 3

Explanation: İki alt massiv var ({5,2} , {7}) ilə hədəf məbləğ kimi 7. Birinci massivin uzunluğu 2, ikinci massiv isə 1-dir. Beləliklə, çıxış 2+1 = 3-dür.

Optimallaşdırılmış Həll

Yanaşma: Biz prefiks cəmi kimi açarı (0-dan i indeksinə qədər bütün massiv elementlərinin cəmini saxlayır) və indeks (i) kimi dəyəri olan hash xəritəsindən istifadə edəcəyik.

  • Birinci dövrədə prefiksdən istifadə edərək massivdən hash xəritəsi yaradın cəmi və indeks.
  • İkinci döngədə əvvəlcə əvvəlki indeksdən cari indeksə qədər olan birinci alt massivi tapın, xəritədə tapın (cari cəmi -hədəf), tapılarsa, birinci alt massivin ölçüsünü yeniləyin min(size, i –) m[cəm-hədəf]).
  • Cari indeksdən ikinci alt massivi tapın, xəritədə (cəm + hədəf) tapın, ikinci alt massivin uzunluğu m[sum+hədəf] olacaq – i.
  • Yekun nəticə : min(res, ölçü + min[cəm+hədəf] -i).

Kodu

C++ Proqramı Hər biri Hədəf Cəmi LeetCode Həlli olan iki üst-üstə düşməyən alt massiv tapın

class Solution {
public:
    int minSumOfLengths(vector<int>& arr, int target) {
        
        unordered_map<int,int> m;
        int n = arr.size();
        int size = n+1;
        int res = n+1;
        m[0] = -1;
        int sum = 0;
        for(int i = 0;i < n;i++)
        {
            sum = sum + arr[i];
            m[sum] = i;
        }
        
        sum = 0;
        for (int i = 0; i < n; i++) 
        {
            sum = sum + arr[i];
            if(m.find(sum - target) != m.end())
                size = min (size, i - m[sum-target]);
            if(m.find(sum + target) != m.end())
                res = min (res, size + m[sum+target]-i);
        }

        if (res == n+1)
          return -1;
        else
          return res;        
    }
};

Java proqramı Hər biri Hədəf Cəmi LeetCode Həlli olan iki üst-üstə düşməyən alt massiv tapın

class Solution {
    public int minSumOfLengths(int[] arr, int target) { 
        
        Map<Integer, Integer> m = new HashMap<>(); 
        int n = arr.length;
        int first_len = n + 1;
        int total = n + 1;
        m.put(0, -1);
        int sum = 0;
        for (int i = 0; i < n; i++) { 
            sum += arr[i];
            m.put(sum, i);
        }
        sum = 0;

        for (int i = 0; i < n; i++) {
            sum = sum + arr[i];
            if (m.containsKey(sum - target)) 
                first_len = Math.min(first_len, i - m.get(sum - target)); 
            if (m.containsKey(sum + target)) 
                total = Math.min(total, first_len + m.get(sum + target) - i); 
        }
        
        if (total == n+1) 
            return -1; 
        else 
            return total;
    }
}

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

Yuxarıdakı kodun Zaman Mürəkkəbliyi O(n)-dir, çünki bu yanaşmada massiv O(n) vaxtında cəmi iki dəfə keçir.

Kosmik Mürəkkəblik

Yuxarıdakı kodun boşluq Mürəkkəbliyi prefiksin cəmini saxlamaq üçün hash xəritəsi üçün O(n)-dir.

Referans: https://en.wiktionary.org/wiki/subarray

Translate »