[Java/C++/Python] Prefix Sum
Intuition\nCalculate the need = sum(A) % p.\nThen one pass, record the prefix sum in a hashmap.\n\n\n# Explanation\nThen the question become:\nFind the shortest
# **Intuition**\nCalculate the `need = sum(A) % p`.\nThen one pass, record the prefix sum in a hashmap.\n<br>\n\n# **Explanation**\nThen the question become:\nFind the shortest array with sum % p = need.\n\n`last[remainder] = index` records the last `index ` that\n`(A[0] + A[1] + .. + A[i]) % p = remainder`\n<br>\n\n# **Complexity**\nTime `O(N)`\nSpace `O(N)`\n<br>\n\n**Java:**\n```java\nclass Solution {\n    public int minSubarray(int[] A, int p) {\n        int n = A.length, res = n, need = 0, cur = 0;\n        for (int a : A)\n            need = (need + a) % p;\n        Map<Integer, Integer> last = new HashMap<>();\n        last.put(0, -1);\n        for (int i = 0; i < n; ++i) {\n            cur = (cur + A[i]) % p;\n            last.put(cur, i);\n            int want = (cur - need + p) % p;\n            res = Math.min(res, i - last.getOrDefault(want, -n));\n        }\n        return res < n ? res : -1;\n    }\n}\n```\n\n**C++:**\n```cpp\n    int minSubarray(vector<int>& A, int p) {\n        int n = A.size(), res = n, need = 0, cur = 0;\n        for (auto a : A)\n            need = (need + a) % p;\n        unordered_map<int, int> last = {{0, -1}};\n        for (int i = 0; i < n; ++i) {\n            cur = (cur + A[i]) % p;\n            last[cur] = i;\n            int want = (cur - need + p) % p;\n            if (last.count(want))\n                res = min(res, i - last[want]);\n        }\n        return res < n ? res : -1;\n    }\n```\n\n**Python:**\n```py\n    def minSubarray(self, A, p):\n        need = sum(A) % p\n        dp = {0: -1}\n        cur = 0\n        res = n = len(A)\n        for i, a in enumerate(A):\n            cur = (cur + a) % p\n            dp[cur] = i\n            if (cur - need) % p in dp:\n                res = min(res, i - dp[(cur - need) % p])\n        return res if res < n else -1\n```\n
[]