A
A
Algorithm Practice
Search…
A
A
Algorithm Practice
Introduction
Lintcode
Leetcode
Google
665 Non-decreasing Array
400 Nth Digit
484 Find Permutation
353 Design Snake Game
348 Design Tic-Tac-Toe
657 Judge Route Circle
789 Escape The Ghosts
667 Beautiful Arrangement II
359 Logger Rate Limiter
463 Island Perimeter
66 Plus One
249 Group Shifted Strings
281 Zigzag Iterator
54 Spiral Matrix
56 Merge Intervals
57 Insert Interval
163 Missing Ranges
228 Summary Ranges
166 Fraction to Recurring Decimal
780 Reaching Points
326 Power of Three
318 Maximum Product of Word Lengths
314 Binary Tree Vertical Order Traversal
297 Serialize and Deserialize Binary Tree
447 Number of Boomerangs
362 Design Hit Counter
448 Find All Numbers Disappeared in an Array
409 Longest Palindrome
406 Queue Reconstruction by Height
370 Range Addition
415 Add Strings
498 Diagonal Traverse
482 License Key Formatting
560 Subarray Sum Equals K
356 Line Reflection
748 Shortest Completing Word
218 The Skyline Problem
391 Perfect Rectangle
481 Magical String
380 Insert Delete GetRandom O(1)
800 Similar RGB Color
246 Strobogrammatic Number
247 Strobogrammatic Number II
465 Optimal Account Balancing
687 Longest Univalue Path
543 Diameter of Binary Tree
777 Swap Adjacent in LR String
792 Number of Matching Subsequences
460 LFU Cache
779 K-th Symbol in Grammar
289 Game of Life
31 Next Permutation
756 Pyramid Transition Matrix
753 Cracking the Safe
330 Patching Array
327 Count of Range Sum
769 Max Chunks To Make Sorted
768 Max Chunks To Make Sorted II
309 Best Time to Buy and Sell Stock with Cooldown
393 UTF-8 Validation
388 Longest Absolute File Path
807 Max Increase to Keep City Skyline
802 Find Eventual Safe States
469 Convex Polygon
683 K Empty Slots
157 Read N Characters Given Read4
158 Read N Characters Given Read4 II - Call multiple times
681 Next Closest Time
317 Shortest Distance from All Buildings
587 Erect the Fence
307 Range Sum Query - Mutable
308 Range Sum Query 2D - Mutable
282 Expression Add Operators
616 Add Bold Tag in String
497 Random Point in Non-overlapping Rectangles
544 Output Contest Matches
386 Lexicographical Numbers
Powered By GitBook
560 Subarray Sum Equals K

1. Question

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
Example 1:
1
Input: nums = [1,1,1], k = 2
2
​
3
Output: 2
Copied!
Note:
  1. 1.
    The length of the array is in range [1, 20,000].
  2. 2.
    The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

2. Implementation

(1) HashTable
1
class Solution {
2
public int subarraySum(int[] nums, int k) {
3
Map<Integer, Integer> map = new HashMap<>();
4
map.put(0, 1);
5
int sum = 0;
6
int res = 0;
7
​
8
for (int num : nums) {
9
sum += num;
10
if (map.containsKey(sum - k)) {
11
res += map.get(sum - k);
12
}
13
map.put(sum, map.getOrDefault(sum, 0) + 1);
14
}
15
return res;
16
}
17
}
Copied!

3. Time & Space Complexity

时间复杂度O(n), 空间复杂度O(n)
Previous
482 License Key Formatting
Next
356 Line Reflection
Last modified 2yr ago
Copy link
Contents
560. Subarray Sum Equals K
1. Question
2. Implementation
3. Time & Space Complexity