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;
    }
}