首页 > 其他分享 >560.和为k的数组

560.和为k的数组

时间:2024-01-18 16:37:10浏览次数:35  
标签:count start 560 nums int 数组 preSum

1.题目介绍

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

2.题解

请注意题目中要求的连续非空序列,要求1.连续 2.非空!!!

2.1 枚举(O(n^2))

思路

最简单的思路是利用双重循环确定数组的开头和结尾,在利用一重循环来进行遍历相加

int count = 0;
for (int start = 0; start <= nums.size(); start++)
{
  for (int end = start; end <= nums.size(); end++)
  {
    int sum = 0;
    for (int i = start; i <= end; i++)
      sum += nums[i];
    if (sum == k) count++;
  }
}

但是这里的时间复杂度达到了O(n^3),必定会超过限制,所以我们进行了一些优化
还是双重循环遍历,确定数组的两个端点
但每次并非从前向后,而是从后向前挨个相加检查。
start确定遍历子数组的右端点,这里end为何不是从0开始,而是从start开始呢?
这样有一个什么好处呢,就是我们每次都有着[j,i]的和
只要再加上nums[j-1],就可以再得到[j-1,i]。
如果end从0开始,其实就和上面的三重循环遍历没有区别了

题解

注意这里找到 sum == k的时候,不可以直接break,因为举个例子[-1,1,0] k = 0; 这时候start指向0这个数,发现sum = k直接break,子数组[-1,1,0]也满足条件但是没有算上!!!

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int count = 0;
        for (int start = 0; start < nums.size(); start++) {
            int sum = 0;
            for (int end = start; end >= 0; end--) {
                sum += nums[end];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
};

2.2 前缀和 + 哈希表优化

思路

关于前缀和是啥,请参考:前缀和
即 存在:preSum[i] = preSum[i-1] + nums[i]
前缀和 就是从 nums 数组中的第 0 位置开始,累加到第 i 位置的结果,我们常把这个结果保存到数组 preSum 中,记为 preSum[i]。

降二重循环为一重循环:
我们可以基于方法一利用数据结构进行进一步的优化,我们知道方法一的瓶颈在于对每个 i,我们需要枚举所有的 j 来判断是否符合条件,所以可以优化为一重循环吗?
我们既然选用一重循环,就面临一个问题,我们只能确定一个参数,这里我们肯定选择区间的右端点,这样的话我们怎么知道其与另一端点构成的子数组和呢?
这里我们利用前缀和的思路去做即可,即我们需要一个数组或者哈希表来保存之前求得的和,即[0,i-1]的和。

这里还有一个问题:子数组可能不是从下标0开始,也有可能是[j,i], 也就是 preSum[i] - preSum[j] = k;
那换个思路是不是我只要用哈希表存储了[0,i-1]每个0开始子数组{如[0,0],[0,1],[0,2]...}的前缀和和其出现次数,
并且加上一个用于表示[0,i]这个数组的键值对{0,1} [preSum[i] -preSum[0]表示的是[1,i],这里我必须加上这个键值对,preSum[i]-0表示的才是[0,i]的值]。
在得到preSum[i] = preSum[i-1] + nums[i]后,由preSum[i] - preSum[j] = k;演变为preSum[j] = preSum[i] - k; 寻找哈希表中值为preSum[i] - k的存在及其出现次数,若存在,将count加上出现次数;不存在,继续遍历即可。

但我们再仔细想想,已经使用了哈希表存储了前缀和及其出现次数,我们还需要用preSum数组来存储前缀和吗?明显是不需要的,我们只需要维护一个前缀和变量pre即可
这里不使用数组存储也是考虑到数组无法快速记录出现次数的问题

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        int count = 0, pre = 0;
        mp[0] = 1;
        for (int i = 0; i < nums.size(); i++){
            pre += nums[i];
            if (mp.count(pre - k)) count += mp[pre-k];
            mp[pre]++;
        }
        return count;
    }
};

标签:count,start,560,nums,int,数组,preSum
From: https://www.cnblogs.com/trmbh12/p/17972778

相关文章

  • PHP把数组按指定的个数分隔
    假设数组为array(‘1’,‘2’,‘3’,‘4’,‘5’,‘6’);想把它分割成四个,那么结果为array( ‘0’=>[‘1’,‘2’], ‘1’=>[‘3’,‘4’], ‘2’=>[‘5’], ‘3’=>[‘6’],);/****把数组按指定的个数分隔*@paramarray$array要分割的数组*@par......
  • 数组遍历的方法
    1、forEach()forEach() 方法对数组的每个元素执行一次给定的函数,不会改变原数组,没有返回值。数组中的每个值都会调用回调函数,回调函数有三个参数:currentValue:必需。当前元素。index:可选。当前元素的索引值。arr:可选。当前元素所属的数组对象。//forEach不会改......
  • python 在排序数组中查找元素的第一个和最后一个位置 多种解法
    二分查找:基于二分查找的算法可以在O(logn)的时间复杂度内解决该问题。具体实现方式是,先使用二分查找找到该元素的位置,然后向左和向右扩展,直到找到第一个和最后一个位置。代码如下:defsearchRange(nums,target):defbinarySearch(nums,target,lower):left,righ......
  • go--数组
    数组的定义数组是用来存储相同唯一类型的,一组已编号且长度固定的序列数组的特点固定长度:这意味着数组不可增长、不可缩减。想要扩展数组,只能创建新数组,将原数组的元素复制到新数组。内存连续:这意味可以在缓存中保留的时间更长,搜索速度更快,是一种非常高效的数据结构,同时还意味......
  • Java数组
    Java数组数组一、数组的声明和创建1、声明dataType[]arrayRefVar;//声明数组2、创建dataType[]arrayRefVar=newdataType[dataSize];//创建一个数组二、初始化及内存分析1、初始化//静态初始化:创建加赋值int[]a={1,2,3};Peo......
  • 将一个数组中的元素头尾两端对调
    #include<stdio.h>voidinplace_swap(int*x,int*y){printf("--------------\n");printf("x=%d,y=%d\n",*x,*y);*y=*x^*y;printf("x=%d,y=%d\n",*x,*y);*x=*x^*y;printf(&......
  • C99标准前后对于二维数组的动态声明问题
    html:toc:true写在前面:出于作者不了解C99以前标准中对二维数组的动态声明而导致的一场考场事故,作者写下这篇文章,,以便其他同学在遇到类似问题时不要犯同样的错误,同时作为对自己的警醒.本文主要是关于对于二维数组动态声明问题在不同C标准下方法的探讨,将给出一个简......
  • 数组Array
    slice用于截取数组的一部分,不修改原数组。letmyArray=[1,2,3,4,5];//使用slice创建一个新的数组,包含索引1到索引3的元素(不包括索引3)letnewArray=myArray.slice(1,3);console.log(newArray);//输出新的数组,这里是[2,3]console.log(myArray);//输出原始数......
  • C# 将字节数组,数值和十六进制字符串相互转换
    byte[]bs=newbyte[32];Randomrandom=newRandom();random.NextBytes(bs);//给字节数组填充随字节stringhex=BitConverter.ToString(bs);//将字节数组转成十六进制字符串,默认-分割Console.WriteLi......
  • python 搜索旋转排序数组 多种解法
    二分查找:旋转排序数组中仍然可以应用二分查找算法。首先,我们找到数组中最小的元素的索引,也就是旋转点的位置。然后,我们根据目标值与旋转点的大小关系,在旋转点的左侧或右侧进行常规的二分查找。defsearch(nums,target):#寻找旋转点left,right=0,len(nums)-1......