560、和为K的子数组

leetcode 数组哈希表前缀和

Created At : 2024-06-02 16:25

Count:760 Views 👀 :

Comment:

题目
1. 示例 1 :
2. 示例 2：
题解
1. 1、枚举法 $O(n^2)$
2. 2、前缀和 + 哈希表优化 $O(n)$

题目

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

子数组是数组中元素的连续非空序列。

示例 1 :

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

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

说明 :

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

链接：https://leetcode-cn.com/problems/subarray-sum-equals-k

题解

1、枚举法 $O(n^2)$

考虑以 i 结尾和为 k 的连续子数组个数，我们需要统计符合条件的下标 j 的个数，其中 $0 <= j <= i$ 且 [j..i] 这个子数组的和恰好为 k 。

双层循环进行枚举：

从头遍历数组
继续遍历累加，直到找到目标值

class Solution {
    public int subarraySum(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) {// 满足要求，结果+1
                    count++;
                }
            }
        }
        return count;
    }
}

2、前缀和 + 哈希表优化 $O(n)$

前缀和是对数组的前缀之和进行存储和复用，达到减少时间复杂度的目的。

数组前缀和pre：累加前一个数字，减少大量的重累加。

两次遍历

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;

        // 求前缀和
        int[] s = new int[n + 1];
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] + nums[i];
        }

        int ans = 0;
        Map<Integer, Integer> cnt = new HashMap<>(n + 1); // 设置容量可以快 2ms
        for (int sj : s) {
            ans += cnt.getOrDefault(sj - k, 0);// 可能是0
            cnt.merge(sj, 1, Integer::sum);// 次数+1
        }
        return ans;
    }
}

一次遍历

class Solution {
    public int subarraySum(int[] nums,int k) {
        int count = 0, pre = 0;
        HashMap<Integer, Integer> mp = new HashMap<>();
        mp.put(0,1);
        for (int i = 0;i < nums.length;i++) {
            pre += nums[i];
            // 如果有已经存在的序列，累加计数器
            if (mp.containsKey(pre - k)) {
                count += mp.get(pre - k);
            }
            // 当前pre前缀和加入map中
            mp.put(pre,mp.getOrDefault(pre,0) + 1);
        }
        return count;
    }
}

特殊解法

原地前缀和
- 顺便求最值
数组哈希表：利用最大最小值，可以构建一个包含所有子串和的哈希表
根据最大最小值，判断是否可以复用已知的子串和

class Solution {
    //和为K的子数组
    public int subarraySum(int[] nums, int k) {
        if(nums.length==0) return 0;
        int max=nums[0];
        int min=nums[0];
        // 求前缀和
        for(int i=1;i < nums.length;i++){
            nums[i] += nums[i-1];
            max = max>nums[i]?max:nums[i];
            min = min<nums[i]?min:nums[i];
        }
        
        int count=0;
        // 数组哈希表
        int[] map=new int[max-min+1];
        for(int i=0;i < nums.length;i++){
            if(nums[i] == k){ // 当前前缀和满足要求
                count++;
            }
            if(nums[i] - k >= min && nums[i] - k <= max){
                // 
                count += map[nums[i]-k-min];
            }
            // 这个怎么理解？
            map[nums[i] - min]++;
        }
        return count;
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com