Today I have done leetcode's December LeetCoding Challenge with cpp.

December LeetCoding Challenge 14

Description

Continuous Subarrays

You are given a 0-indexed integer array nums. A subarray of nums is called continuous if:

• Let i, i + 1, ..., j be the indices in the subarray. Then, for each pair of indices i <= i1, i2 <= j, 0 <= |nums[i1] - nums[i2]| <= 2.

Return the total number of continuous subarrays.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [5,4,2,4]
Output: 8
Explanation: 
Continuous subarray of size 1: [5], [4], [2], [4].
Continuous subarray of size 2: [5,4], [4,2], [2,4].
Continuous subarray of size 3: [4,2,4].
Thereare no subarrys of size 4.
Total continuous subarrays = 4 + 3 + 1 = 8.
It can be shown that there are no more continuous subarrays.

Example 2:

Input: nums = [1,2,3]
Output: 6
Explanation: 
Continuous subarray of size 1: [1], [2], [3].
Continuous subarray of size 2: [1,2], [2,3].
Continuous subarray of size 3: [1,2,3].
Total continuous subarrays = 3 + 2 + 1 = 6.

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

Solution

class Solution {
public:
  long long continuousSubarrays(vector<int>& nums) {
    long long answer = 0;
    int start = 0;
    map<int, int> count;
    for(int end = 0; end < nums.size(); ++end) {
      count[nums[end]] += 1;
      while(count.rbegin()->first - count.begin()->first > 2) {
        answer += end - start;
        count[nums[start]] -= 1;
        if(!count[nums[start]]) count.erase(nums[start]);
        start += 1;
      }
    }
    int len = nums.size() - start;
    answer += 1LL * (len + 1) * len / 2;
    return answer;
  }
};

// Accepted
// 2135/2135 cases passed (99 ms)
// Your runtime beats 74.25 % of cpp submissions
// Your memory usage beats 87.68 % of cpp submissions (112.8 MB)