<p>Given an array of integers <code>nums</code> and an integer <code>k</code>, return <em>the total number of subarrays whose sum equals to</em> <code>k</code>.</p>

<p>A subarray is a contiguous <strong>non-empty</strong> sequence of elements within an array.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> nums = [1,1,1], k = 2
<strong>Output:</strong> 2
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> nums = [1,2,3], k = 3
<strong>Output:</strong> 2
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>-1000 &lt;= nums[i] &lt;= 1000</code></li>
	<li><code>-10<sup>7</sup> &lt;= k &lt;= 10<sup>7</sup></code></li>
</ul>

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> m;
        vector<int> ps(nums.size());
        int prefix{0}, res{0};

        m[0]++;
        for (int i = 0; i < nums.size(); ++i) {
            prefix += nums[i];
            ps.push_back(prefix);

            if (m.count(prefix - k))
                res += m[prefix - k];   
            m[prefix]++;
        }

        return res;

        int l = 0, r = 0;
        int total{0}, sum{0};

        while (r < nums.size()) {
            if (nums[r] == k) total++;
            sum += nums[r];
            if (sum == k) {
                total++;
                while (sum >= k) {
                    sum -= nums[l];
                    l++;
                }
            }
            r++;
        }

        return total;



//         unordered_map<int, int> m;
//         vector<int> sum(nums.size() + 1);
//         int Prefix{0};
//         int res{0};

//         for (int i = 0; i < nums.size(); ++i) {
//             Prefix += nums[i];
//             //sum[i] = Prefix + nums[i];
//             if (m.find(Prefix - k) != m.end()) {
//                     res += m[Prefix - k];
//                     m[Prefix]++;
//             } else {
//                 m[Prefix]++;
//             }
//         }

//     return res;
        

//         int count{0};
//         for (int i = 0; i < nums.size(); ++i) {
//             for (int j = i + 1; j <= nums.size(); ++j) {
//                 if (sum[j] - sum[i] == k) count++;
//             }
//         }

//         return count;

//  /*       std::unordered_map<int, int> m{{0, 1}};
//         int sum = 0, cnt = 0;

//         for (int i = 0; i < nums.size(); ++i) {
//             sum += nums[i];
//             cnt += m[sum - k];
//             m[sum]++;
//         }

//         return cnt;*/

//         std::vector<int> prefix(nums.size());

//         int ct = 0;
//         for (int i = 0; i < nums.size(); ++i) {
//             prefix[i] = nums[i] + (i > 0 ? prefix[i - 1] : 0);

//             cout << prefix[i] << '\n';
//             if (prefix[i] == k) {
//                 if (i > 0) prefix[i] = 0;
//                 ct++;
//             }
//         }

//         return ct;
    }
};
47376