Deque with Picture
Intuition\nThis is similar to 992. Subarrays with K Different Integers.\n\nWhen we find k odd numbers, we have one nice subarray, plus an additional subarray fo
#### Intuition\nThis is similar to [992. Subarrays with K Different Integers](https://leetcode.com/problems/subarrays-with-k-different-integers/discuss/235235/C%2B%2BJava-with-picture-prefixed-sliding-window).\n\nWhen we find `k` odd numbers, we have one nice subarray, plus an additional subarray for each even number preceding the first odd number. This is also true for each even number that follows.\n\nFor example, in the picture below we found `k == 2` odd numbers at index `4`. We have 3 nice subarrays therefore: `[2, 4], [1, 4], [0, 4]`. For even number at index `5`, we also have 3 nice subarrays: `[2, 5], [1, 5], [0, 5]`. Plus 3 subarrays for index `6`.\n\nWhen we encounter `k + 1` odd number at index `7`, we need to get rid of the first odd number (at index `2`) to have exactly `k` odd numbers. So, we count nice subarrays as if the array starts at index `3`. \n\n![image](https://assets.leetcode.com/users/votrubac/image_1572762880.png)\n\n#### Approach 1: Deque\nWe do not have to use `deque`, but it makes tracking the window easier (comparing to moving pointers). Note that in Java, the deque interface does not provide a random access, so we\'ll just use `LinkedList` instead.\n\n**Java**\n```java\npublic int numberOfSubarrays(int[] nums, int k) {\n  LinkedList<Integer> deq = new LinkedList();\n  deq.add(-1);\n  int res = 0;\n  for (int i = 0; i < nums.length; ++i) {\n    if (nums[i] % 2 == 1) \n        deq.add(i);\n    if (deq.size() > k + 1) \n        deq.pop();\n    if (deq.size() == k + 1) \n        res += deq.get(1) - deq.get(0);\n  }\n  return res;\n}\n```\n**C++**\n```cpp\nint numberOfSubarrays(vector<int>& nums, int k, int res = 0) {\n  deque<int> deq = { -1 };\n  for (int i = 0; i < nums.size(); ++i) {\n    if (nums[i] % 2)\n        deq.push_back(i);\n    if (deq.size() > k + 1)\n        deq.pop_front();\n    if (deq.size() == k + 1)\n        res += deq[1] - deq[0];\n  }\n  return res;\n}\n```\n**Complexity Analysis**\n- Time: O(n).\n- Memory: O(k) for the deque.
['C', 'Java']