力扣 - 560. 和为K的子数组

目录

题目

560. 和为K的子数组

思路1(前缀和)

  • 构建前缀和数组,可以快速计算任意区间的和
  • 注意:计算区间时候,下标有变化,计算nums[i..j]之间的和,那么就是sum = prefixSum[j+1] - prefixSum[i],因为prefixSum的0索引位置是0,总的长度比nums大1

代码

class Solution {
    public int subarraySum(int[] nums, int k) {
        int[] prefixSum = new int[nums.length+1];

        for (int i = 0; i < nums.length; i++) {
            prefixSum[i+1] = prefixSum[i] + nums[i];
        }

        int res = 0;
        for (int i = 1; i <= nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (prefixSum[i] - prefixSum[j] == k) {
                    res++;
                }
            }
        }
        return res;
    }
}

复杂度分析

  • 时间复杂度:\(O(N^2)\),其中 N 为数组长度
  • 空间复杂度:\(O(N)\),其中 N 为数组长度

思路2(前缀和+哈希表优化)

  • prefixSum[i] - prefixSum[j] = k 我们可以通过变形成 prefixSum[j] = prefixSum[i] - k
  • 由于只关心具体的次数,而不是解,所以我们可以用哈希表来记录前缀和出现的次数
  • 之前保存了相同前缀和的个数,所以再计算总区间的时候不是再去计算相加,而是符合条件直接从哈希表中找到出现的次数加到res中
  • 这样子时间复杂度就降到了\(O(N)\)了

代码

class Solution {
    public int subarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> prefixSum = new HashMap<>();
        prefixSum.put(0, 1);
        int sumI = 0;
        int res = 0;

        for (int i = 0; i < nums.length; i++) {
            sumI += nums[i];
            // 当前的前缀和(即从0...i)的值减去k,得到的值就是j..i区间的前缀和的值
            int sumJ = sumI - k;
            // 要查找的前缀和看看是否有存在,如果存在说明符合条件,就添加到res中
            if (prefixSum.containsKey(sumJ)) {
                res += prefixSum.get(sumJ);
            }
            // 每次把前缀和的及其出现的次数添加道哈希表中,如果不存在,就初始化为1,存在的话就加1即可
            prefixSum.put(sumI, prefixSum.getOrDefault(sumI, 0) + 1);
        }

        return res;
    }
}

复杂度分析

  • 时间复杂度:\(O(N)\),其中 N 为数组长度
  • 空间复杂度:\(O(N)\),其中 N 为数组长度
上一篇:uboot移植之重定位之前的启动过程


下一篇:金妍解币:12.10比特币以太多空皆有机会今日操作最新分析建议解套