[Leetcode学习]Subarray Sum Equals K(和为K连续子序列)

78 阅读 0 评论 52 点赞

我是靠谱客的博主有魅力柚子，最近开发中收集的这篇文章主要介绍[Leetcode学习]Subarray Sum Equals K(和为K连续子序列)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题：

难度：medium

说明：

给一个数组，求出里面连续子序列和为K的子序列个数，连续子序列就是相当于集合真子集，而且顺序连续的意思。输入数组长度[1, 20,000]，数组元素值范围 [-1000, 1000] ，K值[-1e7, 1e7]（科学记数法）

输入案例：

// 下标 1 2 和为2，下表 2 3 和为2，所以统计为2，两个连续子序列
Input:nums = [1,1,1], k = 2
Output: 2

我的代码：

这个略折腾，幸好之前有借鉴的题目 Contiguous Array。

设置count为统计值，

首先每次相加结果得出sum，

然后map.get (sum-k) 和count相加（因为如果sum随着遍历一直和元素相加，如果之前每出现一次map中已存放的 sumX == (sum - K) ，可以认为从sumX 之后的子序列和为K。）

把每次sum都存到map里面，设置出现次数为 map.get(sum)+ 1（因为可能出现多次相同的sum）

public class SubarraySumEqualsK {
    public static void main(String[] args) {
        Solution solution = new SubarraySumEqualsK().new Solution();
        // 被坑的测试数据
        int[] arr = new int[]{1,2,3,4,5,6,7,1,23,21,3,1,2,1,1,1,1,1,12,2,3,2,3,2,2}; // 12
        int[] arr2 = new int[]{100,1,2,3,4}; // 6
        int[] arr3 = new int[]{28,54,7,-70,22,65,-6};// 100
        int[] arr4 = new int[]{1,1,1}; // 2
        int[] arr5 = new int[]{0,0,0,0,0,0,0,0,0,0}; // 0
        int rtA = solution.subarraySum(arr3, 100);
        System.out.println(rtA);
    }

    class Solution {
        public int subarraySum(int[] nums, int k) {
            int len = nums.length;
            HashMap<Integer, Integer> map = new HashMap<>();
            int sum = 0;
            int count = 0;

            for (int i = 0; i < len; i++) {
                sum += nums[i];
                int d = sum - k;
                // 如果和k相等，先进行相加
                if(sum == k) count ++;
                // 相加map存放次数，因为运行时间没用getOrDefault
                if(map.containsKey(d)) count += map.get(d);
                // 给map次数 + 1
                map.put(sum, map.getOrDefault(sum,0) + 1);           
            }

            return count;
        }
    }
}