剑指 Offer II 010. 和为 k 的子数组

题目链接](剑指 Offer II 010. 和为 k 的子数组 - 力扣（LeetCode） (leetcode-cn.com))

先将前i个元素子数组之和存下来

再用双重循环sum[j]-sum[i]求下标j和下标i之间的子数组和是否为k ,时间复杂度为
O ( n 2 ) O(n^2) O(n2)

class Solution {
    public int subarraySum(int[] nums, int k) {
        int[] sum = new int[nums.length+1];
        int count = 0;
        for(int i = 0; i < nums.length; i++) {
            if(i > 0) sum[i] = nums[i] + sum[i-1];
            else sum[0] = nums[0];
            if(sum[i] == k) count++;
        }//前i个子数组之和
        for(int j = nums.length-1; j >= 0; j--) {
            for(int i = 0; i < j; i++) {
                if(sum[j] - sum[i] == k) count++;
            }
        }
        return count;
    }
}

用HashMap将前num个数的子数组和出现的次数存下来

假设当前前num个数的和为ans，则看前num-1个数中有多少个子数组的和为ans-k，同时剩下的子数组的和就为k

时间复杂度为
O ( N ) O(N) O(N)

public int subarraySum(int[] nums, int k) {
        Map sum = new HashMap<>();
        sum.put(0,1);
        int ans = 0;
        int count = 0;
        for(int num : nums) {
            ans += num;//前num个数之和
            count += sum.getOrDefault(ans-k,0); //前num-1个数中子数组和为ans-k的个数,如果hashmap中不存在ans-k，返回默认值0;
            //存在多少个子数组和为ans-k，即存在多少个子数组和为k
            sum.put(ans,sum.getOrDefault(ans,0)+1);//将当前前num个数之和放入hashmap
        }
        return count;
    }

HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。

实现了 Map 接口。

是无序的，即不会记录插入的顺序。

HashMap 的 key 与 value 类型可以相同也可以不同，可以是字符串（String）类型的 key 和 value，也可以是整型（Integer）的 key 和字符串（String）类型的 value。

HashMap 类位于 java.util 包中，使用前需要引入它，语法格式如下：

import java.util.HashMap; // 引入 HashMap 类

创建HashMap对象

Map sum = new HashMap<>();
// or
HashMap Sites = new HashMap();

 // 创建 HashMap 对象 Sites
 HashMap Sites = new HashMap();
 // 添加键值对
 Sites.put(1, "Google");
 Sites.put(2, "Runoob");
 Sites.put(3, "Taobao");
 Sites.put(4, "Zhihu");//添加元素
 System.out.println(Sites.get(3));//访问键为3元素
 Sites.remove(4);//删除元素
 Sites.clear();//删除所有元素

getOrDefault() 方法获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值。

getOrDefault() 方法的语法为：

hashmap.getOrDefault(Object key, V defaultValue)