Problem
Given an array of integers nums
and an integer k
, return the total number of subarrays whose sum equals to k
.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,1,1], k = 2 Output: 2
Example 2:
Input: nums = [1,2,3], k = 3 Output: 2
Constraints:
1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107
Solution
class Solution {
private HashMap<String, Integer> recipes;
private HashMap<String, Boolean> visitedAndFound; // false to detect cycle
private List<List<String>> ingredients;
private HashSet<String> supplies;
public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
this.recipes = new HashMap<>();
for (int i = 0; i < recipes.length; i++) {
this.recipes.put(recipes[i], i);
}
this.ingredients = ingredients;
this.visitedAndFound = new HashMap<>();
this.supplies = new HashSet<>();
for (String supply : supplies) {
this.supplies.add(supply);
}
List<String> res = new LinkedList<>();
for (String recipe : recipes) {
if (findRecipe(recipe)) {
res.add(recipe);
}
}
return res;
}
public boolean findRecipe(String recipe) {
if (visitedAndFound.containsKey(recipe)) {
return visitedAndFound.get(recipe);
}
visitedAndFound.put(recipe, false);
if (supplies.contains(recipe)) {
visitedAndFound.put(recipe, true);
return true;
}
if (!recipes.containsKey(recipe)) {
return false;
}
for (String ingredient : ingredients.get(recipes.get(recipe))) {
if (findRecipe(ingredient) == false) {
return false;
}
}
visitedAndFound.put(recipe, true);
return true;
}
}