leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0930.cpp (854B)

      1 class Solution {
      2   public:
      3     int numSubarraysWithSum(const vector<int> &nums, int goal) const {
      4         unordered_map<int, int> um = {{0, 1}};
      5         int res = 0, crnt = 0;
      6 
      7         for (const int n : nums) {
      8             crnt += n;
      9             res += um[crnt - goal];
     10             um[crnt]++;
     11         }
     12 
     13         return res;
     14     }
     15 };
     16 
     17 // O(1) space
     18 class Solution {
     19     int atMost(const vector<int> &nums, int goal) const {
     20         if (goal < 0) return 0;
     21 
     22         int res = 0, crnt = 0, i = 0;
     23         for (int j = 0; j < size(nums); j++) {
     24             goal -= nums[j];
     25             while (goal < 0)
     26                 goal += nums[i++];
     27             res += j - i + 1;
     28         }
     29 
     30         return res;
     31     }
     32 
     33   public:
     34     int numSubarraysWithSum(const vector<int> &nums, int goal) const {
     35         return atMost(nums, goal) - atMost(nums, goal - 1);
     36     }
     37 };