最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

经典面试题39_和为 K 的子数组解法思路

XAMPP相关 admin 376浏览 0评论

来源:LeetCode

难度:中等

描述:

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

 

示例1:

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

示例2:

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

分析:

首先,我们考虑下如何在一个整数数组中找到连续的和为k的子数组?

我们肯定是先在左边确定一个起点位置,然后右边的终点位置不断向下延伸,直至终点和起点之间的元素和为k,那么咱们就算找到了一组。然后再调整起点位置,继续按如上操作尝试…,这就是枚举的思路。

上述枚举操作中,咱们每个起点和终点之间的和都需要重新计算,其实咱们可以先将每个位置前面所有元素的和保存下来,当需要计算区间和时,直接用两个位置的前面所有元素的和进行相减即可,这就是前缀和的思路

 

解题

方法一:暴力枚举

思路:

设定两个边界索引 left、right。

先固定左边界left,然后枚举右边界right,当left和right区间内的元素和为k时,计数累积

 

代码:

 1public int subarraySum(int[] nums, int k) {
 2    int count = 0;
 3    int len = nums.length;
 4    //固定左边界
 5    for (int left = 0; left < len; left++) {
 6        int sum = 0;
 7        // 右边姐不断移动
 8        for (int right = left; right < len; right++) {
 9            sum += nums[right];
10            //当left 和right 之间的和为k时 累积计算
11            if (sum == k) {
12                count++;
13            }
14        }
15    }
16    return count;
17}

时间复杂度:O(n2)

空间复杂度:O(1) 

 

方法二:前缀和

思路:

提前构建前缀和数组,在需要求区间和的时候直接进行相减即可

 

代码:

 1public int subarraySum(int[] nums, int k) {
 2    int len = nums.length;
 3
 4    int[] preSum = new int[len + 1];
 5    preSum[0] = 0;
 6    // 计算前缀和数组并保存
 7    for (int i = 0; i < len; i++) {
 8        preSum[i + 1] = preSum[i] + nums[i];
 9    }
10    int count = 0;
11    for (int left = 0; left < len; left++) {
12        for (int right = left; right < len; right++) {
13            // 区间和 [left..right],注意下标偏移
14            if (preSum[right + 1] - preSum[left] == k) {
15                count++;
16            }
17        }
18    }
19    return count;
20}

时间复杂度:O(n2)

空间复杂度:O(n) 

 

以上仅是个人思路解法

转载请注明:XAMPP中文组官网 » 经典面试题39_和为 K 的子数组解法思路

您必须 登录 才能发表评论!