• 力扣560：和为 K 的子数组（Java）

    目录

    一、题目描述

    二、思路讲解

            1、暴力

            2、保存前n个的和

            3、哈希表优化

    一、题目描述

    给你一个整数数组 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

    二、思路讲解

            1、暴力

            算出每一个连续子数组的和即可，超时。

    1. public class Solution {
    2.     public int subarraySum(int[] nums, int k) {
    3.         int count = 0;
    4.         for (int i=0; i
    5.             int sum = 0;
    6.             for (int j=i; j
    7.                 sum += nums[j];
    8.                 if (sum == k) {
    9.                     count++;
    10.                 }
    11.             }
    12.         }
    13.         return count;
    14.     }
    15. }

             时间复杂度：        O(N^2)

             空间复杂度：        O(N)

             

            2、保存前n个的和

            暴力方法超时的原因是我们重复算了很多遍和，是否可以将这些和提前保存下来呢？

            于是想到，我们使用数组sum[]，sum[i]表示数组中前i个数字的和（注意是前i个，而不是索引i之前），我们想要计算某一段子数组的和，比如索引i到j的和，只需计算sum[j+1] - sum[i]即可。

    1. class Solution {
    2.     public int subarraySum(int[] nums, int k) {
    3.         int len = nums.length;
    4.         // int sum = 0;
    5.         int count = 0;
    6.         int []sum = new int[len+1];
    7.         sum[1] = nums[0];
    8.         for(int i=2; i1; i++) {
    9.             sum[i] = sum[i-1] + nums[i-1];
    10.         }
    11.         int left = 0;
    12.         int right = 0;
    13.         for(int i=0; i1; i++) {
    14.             for(int j=i+1; j1; j++) {
    15.                 if((sum[j]-sum[i])==k) {
    16.                     count++;
    17.                 }
    18.             }
    19.         }
    20.         return count;
    21.     }
    22. }

            时间复杂度：        O(N^2)

            空间复杂度：        O(N)        

            3、哈希表优化

            其实，当我们构建好sum数组后，问题转化为了：在sum数组中有几对差为k的数字？不难想到力扣中的第一道题：1. 两数之和-力扣 中使用哈希表优化时间的方式：我们将sum[i]的出现次数保存在哈希表中，然后去寻找sum[i] - k有几个，即可以O(1)的时间复杂度找到。

    1. class Solution {
    2.     public int subarraySum(int[] nums, int k) {
    3.         int len = nums.length;
    4.         int count = 0;
    5.         int []sum = new int[len+1];
    6.         sum[1] = nums[0];
    7.         for(int i=2; i1; i++) {
    8.             sum[i] = sum[i-1] + nums[i-1];
    9.         }
    10.         Map map = new HashMap<>();
    11.         for(int i=0; i1; i++) {
    12.             if(map.containsKey(sum[i]-k)) {
    13.                 count += map.get(sum[i]-k);
    14.             }
    15.             map.put(sum[i], map.getOrDefault(sum[i], 0)+1);
    16.         }
    17.         return count;
    18.     }
    19. }

             时间复杂度：        O(N)

             空间复杂度：        O(N)

  • 相关阅读:
    Shell 文本三剑客 （grep、sed、awk）
    SQL进阶day12——空值处理
    Vue 使用 v-bind 动态绑定 CSS 样式
    《Python3 网络爬虫开发实战》:request(2)
    MySQL（3）
    因斯布鲁克大学团队量子计算硬件突破了二进制
    使用C语言实现循环单链表（带头节点）
    spring 源码编码若干问题
    flutter系列之:在flutter中使用媒体播放器
    音视频数字化（视频的数字化）
  • 原文地址：https://blog.csdn.net/m0_49499183/article/details/128083808