1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

public int subarraySumBruteForce(int[] nums, int k) {
    // 暴力解
    int cnt = 0;

    for (int i = 0; i < nums.length; i++) {
        // 逐个遍历原数组
        int sum = 0;

        for (int j = i; j < nums.length; j++) {
            // 逐个遍历i之后的数据，求和
            sum += nums[j];
            if (sum == k) {
                ++cnt;
            }
        }
    }
    return cnt;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public static int subarraySumPreSum(int[] nums, int k) {
    // 前缀和
    int cnt = 0;

    int[] preSums = new int[nums.length];
    // 首次遍历，生成前缀和数组
    int preSum = 0;
    for (int i = 0; i < nums.length; i++) {
        // 计算前缀和
        preSum += nums[i];
        preSums[i] = preSum;
    }

    // 再遍历前缀和数组，做k等值判断
    for (int left = 0; left < preSums.length; left++) {
        // 外层循环表示左遍历指针，左遍历指针在一轮遍历中固定不变，移动右遍历指针
        int sum;
        for (int right = left; right < preSums.length; right++) {
            sum = right == left ? preSums[right] : preSums[right] - preSums[left];
            if (sum == k) {
                // 只要右区间减去左区间等值，说明满足子数组和为k，同时继续遍历不跳出本轮循环，因为可能有的值为负数，子数组继续增长也有可能满足条件
                ++cnt;
            }
        }
    }

    return cnt;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

public static int subarraySumPreSumMap(int[] nums, int k) {
    int cnt = 0;
    // 未开始遍历数组时，前缀和为0
    int preSum = 0;
    // 使用map存 前缀和->出现次数 的映射；
    Map<Integer, Integer> preSum2Cnt = new HashMap<>(MapUtils.capacity(nums.length));
    preSum2Cnt.put(preSum, 1);

    for (int num : nums) {
        preSum += num;
        // 前缀和-k == 当前位置i元素和减去目标值后的和，
        // 如果这个差值在前面的前缀和中存在，说明子数组和==k，即满足题目条件；
        cnt += preSum2Cnt.getOrDefault(preSum - k, 0);

        // 先判断当前位置-k的前缀和在map中是否已存在；再将当前前缀和放入map；
        preSum2Cnt.put(preSum, preSum2Cnt.getOrDefault(preSum, 0) + 1);
    }

    return cnt;
}