【从零开始刷leetcode-10】 560. 和为 K 的子数组

题目

给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数 

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

示例 1:

输入:nums = [1,1,1], k = 2
输出:2

示例 2:

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

提示:

  • 1 <= nums.length <= 2 * 104
  • -1000 <= nums[i] <= 1000
  • -107 <= k <= 107

解法

解法一 前缀和数组 + 哈希(两数之和)

前缀和数组:子数组 [i, j] 元素的总和 可以用 [0, j] – [0, i] 来计算得到;

哈希优化:参照两数之和的思想,设计一个哈希表,key为 [0, i] 前缀和的值,value为这个前缀和对应的 i 可能的个数;

用一个循环实现:

  1. 构建前缀和数组及次数哈希表
  2. 遍历 nums 数组,查找 preSums[j] – k 的前缀和的次数 (以 j 为终点找符合要求的子数组头部i的个数),因为边构建次数哈希表边进行查找,可以保证不会查询到以j为起点后面的次数,也就是不会重复。
class Solution {
    public int subarraySum(int[] nums, int k) {
        int cnt = 0;
        int[] preSums = new int[nums.length];
        Map<Integer, Integer> map = new HashMap<>();
        // 1 构建前缀和次数Map
        for (int i = 0; i < nums.length; i++) {
            preSums[i] = i==0 ? nums[i] : preSums[i - 1] + nums[i];
            
            // 在构建次数Map之前计算次数,可以保证不会找到自身和后面符合条件的次数。
            if (k == preSums[i]) {
                cnt++;
            }
            if (map.containsKey(preSums[i] - k)) {
                    cnt += map.get(preSums[i] - k);
            }

            // 构建次数Map
            if (!map.containsKey(preSums[i])) {
                map.put(preSums[i], 1);
                continue;
            }
            map.put(preSums[i], map.get(preSums[i]) + 1);
        }
        return cnt;
    }
}

时间复杂度 O(N2)

优化

实际上,不需要实际构建前缀和preSums数组,只要用preSum来保存这一次的前缀和即可。

class Solution {
    public int subarraySum(int[] nums, int k) {
        int cnt = 0;
        int preSum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        // 1 构建前缀和次数Map
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            preSum += nums[i];
            
            // 在构建次数Map之前计算次数,可以保证不会找到自身和后面符合条件的次数。
            if (map.containsKey(preSum - k)) {
                    cnt += map.get(preSum - k);
            }

            // 构建次数Map
            if (!map.containsKey(preSum)) {
                map.put(preSum, 1);
                continue;
            }
            map.put(preSum, map.get(preSum) + 1);
        }
        return cnt;
    }
}

确实得到了小幅度的优化。

小结

  • 计算连续子串的和 ——> 前缀和的思想!

sum[i, j] = preSum[0, j] - preSum[0, i]

  • 两数之和“的思想:要找组成目标和的元素,可以遍历一次数组,用一个元素计算出另一个元素。可以设计一个哈希表,在这个哈希表里面十分高效地查找出来该元素的位置(两数之和)或者出现次数(本题),需要什么就在这个哈希表的value里存什么。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇