题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个整数数组和目标整数 goal，求子数组和恰好为 goal 的子数组数量。

思路分享

  • 这是“恰好型滑动窗口”，本质上就是两个越长越合法的窗口结果之差。

  • 实现有两个方式，一个是单独把滑动窗口划分一个函数，调用两次，求结果之差；另一个是只设置一次滑动窗口，不过要同时维护两个左指针，计算结果是直接累计数值之差。

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 恰好型滑动窗口
class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        int left1 = 0, left2 = 0, ans = 0;
        int sum1 = 0, sum2 = 0;
        int goal1 = goal, goal2 = goal+1;
        for (int right = 0; right < nums.size(); right++) {
            sum1 += nums[right];
            sum2 += nums[right];
            while(sum1 >= goal1&&left1 <= right) {
                sum1-=nums[left1++];
            }
            while(sum2 >= goal2 && left2 <= right) {
                sum2-=nums[left2++];
            }
            ans += left1-left2;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
# 前缀和
class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        s = list(accumulate(nums, initial=0))
        rec = defaultdict(int)
        ans = 0
        # print(s)
        for i in s:
            # print(f"{i} {goal-i} {rec[i - goal]}")
            ans += rec[i - goal]
            rec[i] += 1

        return ans