ผลรวมซับเรย์ขนาดสูงสุดเท่ากับ k


ระดับความยาก กลาง
ถามบ่อยใน Facebook ไมโครซอฟท์
แถว กัญชา hashing

In ผลรวมซับเรย์ขนาดสูงสุดเท่ากับ k เราได้ให้ไฟล์ แถว จำนวนเต็มและค่า k คุณต้องหาความยาวของ subarray ที่ยาวที่สุดซึ่งผลรวมเท่ากับ k หากไม่มี subarray ดังกล่าวให้คืนค่า 0

แนวทางหนึ่งคือใช้แฮชแท็กและตรวจสอบว่าผลรวมเท่ากับ k หรือไม่และส่งกลับความยาวของ subarray ที่มีความยาวเท่ากับ k

ตัวอย่าง:

Input:

ก [] = {10, 5, 2, 7, 1, 9};

k = 15;

Output:

4

คำอธิบาย:

มีอาร์เรย์ย่อยหลายอาร์เรย์ซึ่งผลรวมอาจเป็น 15 เช่น {10, 5}, {5, 1, 9}, {5, 2, 7, 1} แต่ subarray ที่ยาวที่สุดที่มีผลรวม 15 คือ {5, 2, 7, 1} ซึ่งมีความยาว 4.

ผลรวมซับเรย์ขนาดสูงสุดเท่ากับ k

ขั้นตอนวิธี

  1. Tek สองตัวแปรสมมติว่า summation และ length และตั้งค่าเป็นศูนย์เช่น summation = 0, lengths = 0
  2. ประกาศคู่คีย์ - ค่า (แผนที่หรือตารางแฮช)
  3. วนซ้ำจากดัชนี = 0 ถึงดัชนี -1 และดำเนินการต่อด้วยวิธีต่อไปนี้ -
  4. สรุปอาร์เรย์และผลรวมเป็นผลรวม
  5. หากผลรวมพบว่าเท่ากับ k ให้เพิ่มค่าของความยาว 1
  6. ดำเนินการต่อไปโดยมีการตรวจสอบผลรวมหรือไม่หากไม่มีให้เพิ่มเป็นคู่คีย์ - ค่า
  7. ถ้า (summation - k) พบว่ามีอยู่ในแฮชแท็กให้รับดัชนี
  8. หากบรรทัดด้านบนเป็นไปตามนั้นให้อัปเดตค่าของความยาวหากมีความยาว

คำอธิบายสำหรับผลรวม subarray ขนาดสูงสุดเท่ากับ k

นี่จะเป็นวิธีที่มีประสิทธิภาพซึ่งเราสามารถนำโค้ดนี้ไปใช้ด้วยความซับซ้อนของเวลาได้อย่างมีประสิทธิภาพ ดังนั้นแนวคิดหลักของเราคือการใช้ HashMap และตัวแปรบางตัวที่จะเก็บค่าต่างๆไว้ในนั้น

รหัสนี้ใช้สำหรับการวนซ้ำซึ่งดำเนินต่อไปจนกระทั่งถึงความยาวของอาร์เรย์ ขั้นแรกมันจะรวมค่าของ arr [i] แล้วบวกเข้ากับ summation และทำการอัพเดต summation หากค่าของการสรุปพบว่าเท่ากับค่า k มันจะอัปเดตและเพิ่มค่าของความยาวขึ้น 1

บล็อกถัดไปถ้าจะตรวจสอบว่า storeVal (ซึ่งเป็นตัวแปร HashMap) มีค่าของ summation ในแผนที่หรือไม่และหากไม่มี summation เป็นคีย์ในแผนที่ก็จะสร้างรายการในแผนที่และใส่ มูลค่าของการสรุปและดัชนีในแผนที่

ต่อไปถ้าบล็อกจะตรวจสอบว่า storeVal มีคีย์ในรูปแบบของ (summation - k) หรือไม่และถ้าเป็นเช่นนั้นก็จะเปรียบเทียบความยาวกับ (index - storeVal (summation - k)) และถ้าความยาวน้อยกว่า ( index - storeVal (summation - k)) จากนั้นมันจะทำให้ lengths = (index - storeVal (summation - k)) และมันจะดำเนินต่อไปจนกว่าเราจะพบความยาวสูงสุดของ subarray ที่มี summation เท่ากับ k และที่ความยาวของผลตอบแทนสุดท้าย .

สมมติว่าอาร์เรย์ให้:

arr = {10, 5, 2, 7, 1, 9}

ฉัน = 0; ผลรวม = 10, // ผลรวม + = arr [i]

summation == k // (ตรวจสอบ summation เท่ากับ k) // ที่นี่ไม่ใช่

ถ้า (! storeVal.containsKey (sum))

storeVal.put (sum, i) / * ทุกครั้งจะใส่ค่าของ summation และ index เป็นคู่ค่าคีย์ในแผนที่ * /

if (storeVal.containsKey (summation - k)) // ที่นี่ไม่ใช่

และมันจะดำเนินต่อไปและไม่เข้าใน if block จนกว่าจะเป็นไปตามเงื่อนไขและจะเป็นไปตามที่ index = 4 และการดำเนินการบางอย่างจะดำเนินการและเราได้รับคำตอบที่ถูกต้อง

การนำไปใช้งานใน C ++ สำหรับผลรวมซับเรย์ขนาดสูงสุดเท่ากับ k

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int lenOfSubArray(int arr[], int n, int k)
{
  int summation = 0, lengths = 0;
  map<int, int> storeVal;
  for (int index = 0; index < n; index++)
  {
    //sums up the array
    summation += arr[index];
    //check if summation is equals to k
    if (summation == k)
    {
      lengths = index + 1;
    }

    if (storeVal.find(summation) == storeVal.end())
    {
      //store the values as a key value pair in
      //map
      storeVal[summation] = index;
    }

    if (storeVal.find(summation - k) != storeVal.end())
    {
      //updation of lengths
      if (lengths < (index - storeVal[summation - k]))
      {
        lengths = index - storeVal[summation - k];
      }
    }
  }

  return lengths;
}

int main()
{
  int arr[] = { 2, 5, 7, 3, 7, 9, 1 };
  int k = 17;
  int n = sizeof(arr) / sizeof(arr[0]);
  cout << "Length of Longest Substring is:" << lenOfSubArray(arr, n, k);
  return 0;
}
Length of Longest Substring is: 4

การนำไปใช้งานใน java สำหรับผลรวม subarray ขนาดสูงสุดเท่ากับ k

import java.util.*;
import java.io.*;
class findMaxSubArray {
    public static int lenOfSubArray(int arr[], int n, int k) {
        int summation = 0, lengths = 0;
        HashMap<Integer, Integer> storeVal = new HashMap<>();
        for (int index = 0; index<n; index++) {
            //sums up the array
            summation += arr[index];
            //check if summation is equals to k
            if (summation == k) {
                lengths = index + 1;
            }
            if (!storeVal.containsKey(summation)) {
                //store the values as a key value pair in
                //map
                storeVal.put(summation, index);
            }
            if (storeVal.containsKey(summation - k)) {
                //updation of lengths
                if (lengths<(index - storeVal.get(summation - k))) {
                    lengths = index - storeVal.get(summation - k);
                }
            }
        }
        return lengths;
    }
    //Driver code
    public static void main(String args[]) {
        int arr[] = { 2, 5, 7, 3, 7, 9, 1 };
        int k = 17;
        int n = arr.length;
        System.out.println("Length of Longest Substring is:" + lenOfSubArray(arr, n, k));
    }
}
Length of Longest Substring is:4

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

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

 O (n) โดยที่ n คือขนาดของอาร์เรย์

พื้นที่เสริม

 O (n) โดยที่ n คือขนาดของอาร์เรย์

อ้างอิง