leetcode/src/solution/medium/P560_Subarray_Sum_Equals_K.java at master · Yi-Lo/leetcode · GitHub

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
package solution.medium;

import java.util.HashMap;

/**
 * @author Yi-Lo
 * 2021/1/12 10:42
 * @version 1.0
 * @topics Array、Hash Table
 * @urllink https://leetcode-cn.com/problems/subarray-sum-equals-k/
 */
public class P560_Subarray_Sum_Equals_K {

    public static int subarraySum_s1(int[] nums, int k) {
        int n = nums.length, count = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < n; j++) {
                int sum = 0;
                if (i + j > n) break;
                for (int m = 0; m < i; m++) {
                    sum += nums[j + m];
                }
                if (sum == k) count++;
            }
        }
        return count;
    }

    public static int subarraySum_s2(int[] nums, int k) {
        int count = 0;
        for (int start = 0; start < nums.length; start++) {
            int sum = 0;
            for (int end = start; end >= 0; end--) {
                sum += nums[end];
                if (sum == k) count++;
            }
        }
        return count;
    }

    public static int subarraySum_s3(int[] nums, int k) {
        int count = 0, preSum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            preSum += nums[i];
            if (map.containsKey(preSum - k)) {
                count += map.get(preSum - k);
            }
            map.put(preSum, map.getOrDefault(preSum, 0) + 1);
        }
        return count;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        System.out.println(subarraySum_s1(nums, 5));
        System.out.println(subarraySum_s2(nums, 5));
        System.out.println(subarraySum_s3(nums, 5));
    }
}