By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、和为K的子数组

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

说明 :数组的长度为 [1, 20,000]。

  数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

​

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

1.1、解题思路

和算法和可被K整除的连续子数组有些像，都是连续的求解

1.2、算法

public int subarraySum(int[] nums, int k) {
    int count = 0, sum = 0;
    HashMap<Integer, Integer> mp = new HashMap<>();
    //这个很关键，只因为下面要判断是否存在，如果sum 等于 k，则表示肯定会存在，所以必须提前放入
    mp.put(0, 1);
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (mp.containsKey(sum - k)) {
            count += mp.get(sum - k);
        }
        mp.put(sum, mp.getOrDefault(sum, 0) + 1);
    }
    return count;
}

1.3、测试

  @Test
    public void test(){
        // int nums[] = {1,1,1};
        // int nums[] = {1,2,3};
        int nums[] = {0,0,0,0,0,0,0,0,0,0};

        System.out.println(subarraySum(nums, 3));
    }

​

ContactAuthor