Analysis and explanation with Visualization
How many subarrays are there in an array of size N? (subarrays can have size >= 1 up to N)\n  \n   \n   There are n * (n + 1) / 2 subarrays in an array of size 
- How many subarrays are there in an array of size N? (subarrays can have size >= 1 up to N)\n  \n   ```\n   There are n * (n + 1) / 2 subarrays in an array of size N. \n   Example: A = [1,2,3,4]\n   Subarrays: [1] [2] [3] [4] [1,2] [2,3] [3,4] [1,2,3] [2,3,4]\n              Subarrays of size 1: 4\n              Subarrays of size 2: 3\n              Subarrays of size 3: 2\n              Subarrays of size 4: 1\n              Total subarrays: 4 + 3 + 2 + 1 or 1 + 2 + 3 + 4\n              Which translates to: sum of the first N natural numbers where N is the size of the array\n   ```\n\n- Compute subarrays of size at most k in array of size N:\n   Solution: use the idea above and the sliding window technique. When our map exceeds k, we shrink it from the left side. In each iteration that we move the end point, we are computing the sum above (1 + 2 + 3 + ---- until end pointer). \n\n   ```csharp\n   public int AtMostK(int[] s, int k) {\n          Console.WriteLine("k = " + k);\n\n          int res = 0;\n          Dictionary<int, int> map = new Dictionary<int, int>();\n          int start = 0, end = 0;\n          while (end < s.Length) {\n              if (!map.ContainsKey(s[end])) {\n                  map.Add(s[end], 0);\n              }\n\n              map[s[end]]++;\n\n              while (map.Count > k) {\n                  map[s[start]]--;\n                  if (map[s[start]] == 0) {\n                      map.Remove(s[start]);\n                  }\n                  start++;\n              }\n\n              res += end - start + 1;\n              Console.Write("[");\n              for (int i = start; i <= end; i++) {\n                  Console.Write(s[i] + (i == end ? "" : ","));\n              }\n              Console.WriteLine("]");\n\n              end++;\n          }\n\n          return res;\n      }\n   ```\n  \n - Compute subarrays of size EXACTLY K from an array of size N. \n  Solution: Compute subarrays of size AT MOST K and subtract subarrays of size AT MOST K - 1.\n  Why? atMostK(A, k) includes subarrays of size 1, 2, 3, .... k - 1 (all subrrays with size less than K). How to get rid of those arrays that have size less than K? Compute subarrays of size K - 1 which will give you subarrays of size 1, 2, 3, .... k - 2. The subarrays that we don\'t want from the first list will be cancelled out by the subarrays in the second list. \nVisualization: \n![image](https://assets.leetcode.com/users/benevolent/image_1591429158.png)\n\nTherefore, we need to call the above function once with K and once with K - 1, and subtract the results:\nFinal solution: \n```csharp\n return AtMost(s, k) - AtMost(s, k - 1)\n```\n
[]