leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0930.cpp (854B)

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