Subarray Sum ต่อเนื่องใน C ++

สมมติว่าเรามีรายการตัวเลขที่ไม่เป็นลบและจำนวนเต็มเป้าหมาย k เราต้องเขียนฟังก์ชันเพื่อตรวจสอบว่าอาร์เรย์มี subarray ย่อยต่อเนื่องที่มีขนาดอย่างน้อย 2 ที่ผลรวมเป็นทวีคูณของ k รวมกันได้ไม่เกิน n* k โดยที่ n เป็นจำนวนเต็มด้วย ดังนั้นหากอินพุตเป็น [23,2,4,6,7] และ k =6 ผลลัพธ์จะเป็น True เนื่องจาก [2,4] เป็นอาร์เรย์ย่อยต่อเนื่องของขนาด 2 และผลรวมสูงสุด 6

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้างแผนที่ m ตั้งค่า m[0] :=-1 และ sum :=0, n :=ขนาดของอาร์เรย์ nums
• สำหรับ i ในช่วง 0 ถึง n – 1
  • sum :=sum + nums[i]
  • ถ้า k ไม่ใช่ศูนย์ ให้ sum :=sum mod k
  • ถ้า m มีผลรวม และ i – m[sum]>=2 แล้วคืนค่าเป็นจริง
  • ถ้า m ไม่มีผลรวม ให้ตั้งค่า m[sum] :=i
• คืนค่าเท็จ

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool checkSubarraySum(vector<int>& nums, int k) {
      unordered_map<int, int> m;
      m[0] = -1;
      int sum = 0;
      int n = nums.size();
      for(int i = 0; i < n; i++){
         sum += nums[i];
         if(k)
         sum %= k;
         if(m.count(sum) && i - m[sum] >= 2){
            return true;
         }
         if(!m.count(sum)) m[sum] = i;
      }
      return false;
   }
};
main(){
   vector<int> v = {23,2,4,6,7};
   Solution ob;
   cout << (ob.checkSubarraySum(v, 6));
}

อินพุต

[23,2,4,6,7]
6

ผลลัพธ์

1