Subarray Sum K
最后更新于:2022-04-02 01:08:10
# Subarray Sum K
### Source
- GeeksforGeeks: [Find subarray with given sum - GeeksforGeeks](http://www.geeksforgeeks.org/find-subarray-with-given-sum/)
~~~
Given an nonnegative integer array, find a subarray where the sum of numbers is k.
Your code should return the index of the first number and the index of the last number.
Example
Given [1, 4, 20, 3, 10, 5], sum k = 33, return [2, 4].
~~~
### 题解1 - 哈希表
题 [Zero Sum Subarray | Data Structure and Algorithm](http://algorithm.yuanbin.me/zh-cn/integer_array/zero_sum_subarray.html) 的升级版,这道题求子串和为 K 的索引。首先我们可以考虑使用时间复杂度相对较低的哈希表解决。前一道题的核心约束条件为 f(i1)−f(i2)=0f(i_1) - f(i_2) = 0f(i1)−f(i2)=0,这道题则变为 f(i1)−f(i2)=kf(i_1) - f(i_2) = kf(i1)−f(i2)=k
### C++
~~~
#include
#include
#include
';