cpp-codes/Array_Leetcode_Subarray_Sum_K_560.cpp at master · abhinavkumaryadav1/cpp-codes · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/*560. Subarray Sum Equals K

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2
Example 2:

Input: nums = [1,2,3], k = 3
Output: 2


Constraints:

1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107*/

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
      //only works for positive element so we cant use this it will fail for negative numbers
    //  int i =0;
    //  int j=0;
    //  int n = nums.size();
    //  int curr =0;
    //  int cnt=0;

    //  if(n==1)
    //  {
    //   if(k==nums[0])
    //   {
    //     return 1;
    //   }
    //   else return 0;
    //  }

    //  while(i<n && j<n)
    //  {

    //   curr += nums[i];

    //   if(curr==k)
    //   {
    //     cnt++;
    //   }
    //   while(curr>k)
    //   {
    //     curr -= nums[j];
    //     j++;
    //     if(curr==k)
    //   {
    //     cnt++;
    //   }
    //   }


    //   i++;
    //  }

    //   return cnt;

    //optimal approch prefix sum approch very important

    unordered_map<int,int> m;
    m[0] = 1;

    int cnt =0;
    int sum =0;
    int n= nums.size();

    for(int i =0 ; i<n;i++)
    {
      sum += nums[i];

      if(m.find(sum-k) != m.end()) //jo bhi sum aya hai usme se k subtract karo jo number aye wo map me hona chaiye kyunki hume 0 banana hai -> 0 banaya matlab ye subarray K ke barabar hai.
      {
        cnt += m[sum-k];
      }

      m[sum]++; //prefix sum store kara reh hai map me thoda sa alag hai k-sum wale se
    }
        return cnt;
    }
};