专栏首页健程之道力扣560——和为K的子数组

力扣560——和为K的子数组

这道题主要是找规律,优化的时候可以利用哈希表和数组的特性。

原题

给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

说明 :

  1. 数组的长度为 [1, 20,000]。
  2. 数组中元素的范围是 [-1000, 1000] ,且整数 k 的范围是 [-1e7, 1e7]。

原题url:https://leetcode-cn.com/problems/subarray-sum-equals-k/

解题

一开始的想法肯定就是利用暴力解法了,三层 for 循环的那种,第1层和第2层选择起点和终点,第3层则是计算起点到终点的总和。这样的想法最简单,但很可惜,直接超时了,让我们稍微优化一下。

子数组之和

因为题目要求子数组下标连续,那么我们想想,如果要求sum(i, j)(也就是从下标 i 到下标 j 的子数组之和),其实可以转化成sum(0, i - 1) - sum(0, j)。这样的话,就可以把上面的三层for循环优化成两层。

接下来我们直接看看代码:

class Solution {
    public int subarraySum(int[] nums, int k) {
        // sum(i, j) = sum(0, j) - sum(0, i - 1)
        int[] sumArray = new int[nums.length];
        sumArray[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sumArray[i] = sumArray[i - 1] + nums[i];
        }

        int result = 0;
        int sum = 0;
        for (int i = sumArray.length - 1; i >= 0; i--) {
            // 前i个数之和
            if (sumArray[i] == k) {
                result++;
            }
            // 查询从(j + 1)到i的和
            for (int j = i - 1; j >= 0 && j != i; j--) {
                sum = sumArray[i] - sumArray[j];
                if (sum == k) {
                    result++;
                }
            }
        }
        return result;
    }
}

提交OK,但时间复杂度是O(n^2),优化一下。

用哈希表优化

我们想想,上面使用使用第二层for循环,主要是为了查出 sumArray 中是否还存在等于sumArray[i] - k的数,这明显是一个映射关系,因此我们用一个 map 去记录中间的求和结果。

class Solution {
    public int subarraySum(int[] nums, int k) {
        // sum(i, j) = sum(0, j) - sum(0, i - 1)
        // 用map存储,key为sum,value为第i个数
        Map<Integer, List<Integer>> map = new HashMap<>(nums.length * 4 / 3 + 1);
        // 数组求和
        int sum = 0;
        // 记录一共有哪些和
        Set<Integer> sumSet = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            sumSet.add(sum);
            // 查看当前是否已经记录
            List<Integer> indexList = map.get(sum);
            if (indexList == null) {
                indexList = new LinkedList<>();
            }
            indexList.add(i);
            map.put(sum, indexList);
        }

        int result = 0;
        for (Integer subSum : sumSet) {
            List<Integer> list = map.get(subSum);
            // 如果list为null,说明是被移除了,说明之前已经计算过
            if (list == null) {
                continue;
            }
            if (subSum == k) {
                result += map.get(subSum).size();
            }
            // 剩余的和
            int remainSum = subSum - k;
            List<Integer> remainList = map.get(remainSum);
            // 如果为null,说明不存在
            if (remainList == null) {
                continue;
            }

            // 如果不为null,说明存在,则可以进行配对
            // 让list和remainList进行配对
            for (int index1 : list) {
                for (int index2 : remainList) {
                    if (index1 <= index2) {
                        continue;
                    }

                    result++;
                }
            }
        }
        return result;
    }
}

提交OK,虽然较之前的方法时间效率上有所提高,但并没有本质区别。特别是最后的双重 for 循环,因为下标只有大的减小的才有意义,这样也就给自己额外增加了运算。

那么反思一下,是否真的有必要提前算好子数组的和?如果一边遍历一边求和,并将求和的结果存入map中,那么 map 中存在的,一定是下标小于自己的求和结果。针对这点,我们可以再做一步优化:

public class Solution {
    public int subarraySum(int[] nums, int k) {
        // 最终结果的数量
        int count = 0;
        // 求和
        int sum = 0;
        // key为中间求出了哪些和,value为当前和有几种情况
        HashMap<Integer, Integer> map = new HashMap<>();
        // 和为0有1种情况,就是一个数都不选
        map.put(0, 1);
        // 遍历数组
        for (int i = 0; i < nums.length; i++) {
            // 求和
            sum += nums[i];
            // map中是否有记录剩余的值
            if (map.containsKey(sum - k)) {
                // 累加,此处可以直接添加,是因为求和是从前往后进行的,现在能找到的,说明一定是之前的
                count += map.get(sum - k);
            }
            // 记录当前的值
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}

提交OK,这样时间复杂度就变为了O(n)

数据结构的优化

现在,我们用哈希表来存储中间结果。虽然哈希表的查找效率理论上可以达到O(1),但考虑到哈希冲突,最坏情况下还是有可能达到O(n)。真正能够保证达到O(1)的数据结构,是数组(用空间换取时间)。

那这个用来存储的一维数组究竟长度该设置为多少呢?自然就是找出数组中子数组之和的最大值和最小值,两者求差,结果就是最终的数组长度。利用这个数组去存储子数组求和的结果,这样就能保证在查找时的效率了。

class Solution {
    public int subarraySum(int[] nums, int k) {
        int sum = 0;
        // sum的最小值和最大值,因为可以一个数值都不选,因此0作为初始值
        int min = 0;
        int max = 0;
        // 求和
        for (int n : nums) {
            sum += n;
            min = Math.min(min, sum);
            max = Math.max(max, sum);
        }
        // sums[i]代表从下标为0到下标为i的子数组之和
        // 用一个数组存储,相比于map,取值更快,用空间换取时间
        int[] sums = new int[max - min + 1];
        // 最终结果
        int count = 0;
        sum = 0;
        // 遍历数组
        // 需要重新求和,因为没有类似set这样的结构存储了结果
        for (int n : nums) {
            // 求和
            sum += n;
            // 新的目标值
            int target = sum - min - k;
            // 是否有超过范围
            if (target >= 0 && target < sums.length) {
                count += sums[target];
            }

            sums[sum - min]++;
        }
        // 再加上本身就是k的子数组的数量
        if (k - min >= 0 && k - min < sums.length) {
            count += sums[k - min];
        }
        return count;
    }
}

提交OK,执行时间上更快了。

总结

以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题主要是找规律,优化的时候可以利用哈希表和数组的特性。

有兴趣的话可以访问我的博客或者关注我的公众号、头条号,说不定会有意外的惊喜。

https://death00.github.io/

本文分享自微信公众号 - 健程之道(JianJianCoder),作者:健健壮

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 力扣494——目标和

    给定一个非负整数数组,a1, a2, ..., an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一...

    健程之道
  • 力扣213——打家劫舍 II

    你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有...

    健程之道
  • Java面试-动态规划与组合数

    最近在刷力扣上的题目,刷到了65不同路径,当初上大学的时候,曾在hihocoder上刷到过这道题目,但是现在已经几乎全忘光了,大概的知识点是动态规划,如今就让我...

    健程之道
  • LeetCode268. 缺失数字

    mathor
  • LeetCode 494. 目标和(DFS+DP)

    给定一个非负整数数组,a1, a2, …, an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符...

    Michael阿明
  • 最大子序列和(leetcode)

    euclid
  • 【Code】关关的刷题日记22——Leetcode 53. Maximum Subarray

    关小刷刷题 22——Leetcode 53. Maximum Subarray 题目 Find the contiguous subarray within a...

    WZEARW
  • 方法的定义及调用

    葆宁
  • [翻译]Bitmap的异步加载和缓存

    内容概述 [翻译]开发文档:android Bitmap的高效使用 本文内容来自开发文档“Traning > Displaying Bitmaps Effic...

    用户1172465
  • 十大经典排序算法整理汇总(附代码)

    本文整理并总结了十大经典的排序算法(冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、计数排序、基数排序、桶排序、堆排序)的时间复杂度、空间复杂度等性...

    godweiyang

扫码关注云+社区

领取腾讯云代金券