【LeetCode】第560题：和为K的子数组

本是古典何须时尚 2021-12-11 15:57 305阅读 0赞

LeetCode 链接：[https://leetcode-cn.com/problems/subarray-sum-equals-k/comments/][https_leetcode-cn.com_problems_subarray-sum-equals-k_comments]

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

> 示例 1 :
> 
> 输入:nums = \[1,1,1\], k = 2  
> 输出: 2 , \[1,1\] 与 \[1,1\] 为两种不同的情况。  
> 说明 :
> 
> 数组的长度为 \[1, 20,000\]。  
> 数组中元素的范围是 \[-1000, 1000\] ，且整数 k 的范围是 \[-1e7, 1e7\]。

## 1、暴力解【时间复杂度 O(N^2)】 ##

从头开始遍历数组，每个 i 位置都会作为一个 sum 的开头，依次往后遍历，看能否累加出 sum = k 的情况。这里需要说明的是因为存在负数和连续0的情况，所以几遍出现了 sum > k 的情况，但是依然要遍历完整个 i 之后的数据。

public class SubArrSumToK_560 {
    
        public static int subarraySum(int[] nums, int k) {
            if(nums == null || nums.length < 1){
                return -1;
            }
    
            int count = 0;
            for(int i = 0; i < nums.length; i++){
                int sum = 0;
                for(int j = i; j < nums.length; j++){
                    if(nums[j] + sum == k){
                        count++;
                        // 可能存在{0,0,0,0,0,0,0,0} 0 的情况，所以还需要继续累加
                        sum += nums[j]; 
                    }else{
                        // 可能存在负数，所以不管sum是大于还是小于k，都要继续累加
                        sum += nums[j];  
                    }
                }
            }
            return count;
        }
    
        public static void main(String[] args) {
            int[] arr = {1, 1, 1};
            System.out.println(subarraySum(arr, 2));  // 2
        }
    }

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

## 2、Map 实现（时间复杂度 O(N)） ##

1、建立 map 表用于存储每个连续子数组 sum 求和出现的次数，初始化为（0,1），表示和为 0 的连续子数组出现 1 次；

2、sum 的值是在对 nums 数组的循环中不断累加当前元素的，res 的值则需要查找 map 中是否已存在和为 sum - k 的连续数组，也就是在查找此前所有从 0 项开始累加的连续子项和中有没有 sum - k。

3、如果有的话，则说明从该项到当前项的连续子数组和必定为 k，那么 res 则可以和这个 sum 的对应值，即这个 sum 出现的次数，相加得到新的 res。

4、对于当前 sum 如果已存在与 map 中则其对应值 +1，不存在则添加新项，初始值为 1。

>  *  可能直观上不太容易理解，主要的困惑点在于为什么每次都要从头开始累加连续的子数组，那么这样处在中间位置的连续子数组还能找到呢？结果是可以的，因为每个 preSum 都是从头累加过来的，只要出现 preSum = sum - k，的情况，那么肯定存在和为 k 的连续子数组，因为 sum 也是从头开始一路累加过来的，preSum 其实代表的就是每个数组从头位置累加到 i  位置的和。
> 
> **map 中的 key 存的是前缀为 x，value存的是前缀为x的连续子数组的个数，pi = a\[0\] + a\[1\] + ... + a\[i\]，pj =  a\[0\] + a\[1\] + ... + a\[j\]。当 pj - pi = a\[i + 1\] + a\[i + 2\] + ... + a\[ j \] = K，只需要知道前面有几个 sum - k 的个数，就是所求的结果。**

public class SubArrSumToK_560 {
    
        // Map 实现
        public static int subArraySum(int[] nums, int k){
            int sum = 0;
            int res = 0;
            Map<Integer, Integer> preSum = new HashMap<>();
            preSum.put(0, 1);
            for(int i = 0; i < nums.length; i++){
                sum += nums[i];
                // 判断是否存在和为sum - k的连续式数组，如果存在，那么一定存在和为k的连续数组
                // 每次都是从数组起始位置累加的
                if(preSum.containsKey(sum - k)){
                    res += preSum.get(sum - k);
                }
                // 如果不存在sum-k的连续子数组，则将sum的连续子数组存进preSum里
                preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
            }
            return res;
        }
    
        public static void main(String[] args) {
            int[] arr = {9, 2, 3, 5, 9, 3, 8, 4};
            System.out.println(subArraySum(arr, 10));  // 1
        }
    }

[https_leetcode-cn.com_problems_subarray-sum-equals-k_comments]: https://leetcode-cn.com/problems/subarray-sum-equals-k/comments/