LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k）

向右看齐 2022-04-05 06:28 174阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。
> 
> 这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：42. Trapping Rain Water（能装多少水问题）][LeetCode_42. Trapping Rain Water]**

--------------------

**文章目录：**

题目描述：

java实现方式1：

python实现方式1：

java实现方法2：

python实现算法2：

源码地址：

--------------------

### 题目描述： ###

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

示例 1 :

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

说明 :

数组的长度为 \[1, 20,000\]。  
数组中元素的范围是 \[-1000, 1000\] ，且整数 k 的范围是 \[-1e7, 1e7\]。

来源：力扣（LeetCode）

--------------------

## 方法一 ：使用累计和  ##

--------------------

对于每个考虑的新子数组，我们不是每次都计算元素的总和，而是使用累积和数组 sum。然后，为了计算位于两个索引之间的元素之和，我们可以减去对应于两个索引的累积和以直接获得总和，而不是迭代子数组以获得总和。

### java实现方式： ###

/**
         * 求和
         *
         * @param nums 数组
         * @param k    k个数
         * @return 数字和
         */
        public int subarraySum1(int[] nums, int k) {
            int count = 0;
            for (int i = 0; i < nums.length; i++) {
                int sum = 0;
                for (int j = i; j < nums.length; j++) {
                    sum = sum + nums[j];
                    if (sum == k) {
                        count++;
                    }
                }
            }
            return count;
        }

**时间复杂度：**O(n^2)，考虑每个可能的子数组需要 O(n ^ 2)时间，在初始处理 O(n) 之后，找出任何子数组的总和需要 O(1)时间来创建累积和数组。

**空间复杂度：**O(n)，使用累积和数组 sum，大小为 n + 1。

--------------------

### python实现方式： ###

def subarray_sum_equals_k(nums: List[int], k: int) -> int:
        '''
            找出和相同的数组
        Args:
            nums:数组
            k:固定值
        Returns:
            数组种数
        '''
        count, length = 0, len(nums)
        for i in range(length):
            total = 0
            for j in range(i, length):
                total += nums[j]
                if total == k:
                    count += 1
        return count

**时间复杂度：**O(n^2)，考虑每个可能的子数组需要 O(n ^ 2)时间，在初始处理 O(n) 之后，找出任何子数组的总和需要 O(1)时间来创建累积和数组。

**空间复杂度：**O(n)，使用累积和数组 sum，大小为 n + 1。

--------------------

## 方法二： 采用哈希表 ##

利用hashmap的形式保存值：

这种方法背后的想法如下：如果累积总和最多两个指数是相同的，那么这些元素之间的元素总和为零。进一步扩展相同的想法，如果累计总和，在索引 i 和 j处相差 k，即 sum\[i\] - sum\[j\] = k，则位于索引 i 和 j之间的元素之和是 k。

基于这些想法，可以使用了一个哈希表 map，它用于存储所有可能的索引的累积总和以及相同累加和发生的次数。我们以以下形式存储数据：(sumi，sumi的出现次数)。我们遍历数组nums并继续寻找累积总和。每当我们遇到一个新的和时，我们在hashmap中创建一与该总和相对应的新条目。如果再次出现相同的和，我们增加与map中的和相对应的计数。此外，对于遇到的每个总和，我们还确定已经发生 sum-k 总和的次数，因为它将确定具有总和 k 的子阵列发生到当前索引的次数。我们将 count 增加相同的量，在完成便利数组后，count 记录了所需结果。

--------------------

### java实现方法2： ###

/**
         * 求和
         *
         * @param nums 数组
         * @param k    k个数
         * @return 数字和
         */
        public int subarraySum(int[] nums, int k) {
            int count = 0;
            int sum = 0;
            HashMap<Integer, Integer> map = new HashMap<>();
            map.put(0, 1);
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
                if (map.containsKey(sum - k)) {
                    count += map.get(sum - k);
                }
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
            return count;
        }

**时间复杂度：**O(n)，数组 nums 仅需遍历一遍。

**空间复杂度：**O(n)，哈希表 map 在最坏情况下可能有 n 个不同的键值。

--------------------

### python实现算法2： ###

def subarray_sum_equals_k(nums: List[int], k: int) -> int:
        '''
            找出和相同的数组
        Args:
            nums:数组
            k:固定值
        Returns:
            数组种数
        '''
        count, total = 0, 0
        map = {}
        map[0] = 1
        for i in range(len(nums)):
            total += nums[i]
            if (total - k) in map:
                count += map[total - k]
            if total not in map:
                map[total] = 1
            else:
                map[total] = map[total] + 1
        return total

**时间复杂度**：O(n)，数组 nums 仅需遍历一遍。

**空间复杂度：**O(n)，哈希表 map 在最坏情况下可能有 n 个不同的键值。

--------------------

### 源码地址： ###

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_42. Trapping Rain Water]: https://blog.csdn.net/zy345293721/article/details/85164977
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode