leetcode

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 };