413. Arithmetic Slices

2020, Dec 05 2 mins read

1. Description

An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, [1,3,5,7,9], [7,7,7,7], and [3,-1,-5,-9] are arithmetic sequences.

Given an integer array nums, return the number of arithmetic subarrays of nums.
A subarray is a contiguous subsequence of the array.

2. Example

Example 1

Input: nums = [1,2,3,4]
Output: 3
Explanation: We have 3 arithmetic slices in nums: [1, 2, 3], [2, 3, 4] and [1,2,3,4] itself.

Example 2

Input: nums = [1]
Output: 0

3. Constraints

1 <= nums.length <= 5000
-1000 <= nums[i] <= 1000

4. Solutions

Two Pointers

n = nums.size()
Time complexity: O(n)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int numberOfArithmeticSlices(const vector<int> &nums) {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);

        if (nums.size() == 1) {
            return 0;
        }

        int result = 0;
        int left = 0, right = 1, diff_count = 0;
        for (int diff = nums[right] - nums[left]; right < nums.size();) {
            if (nums[right] - nums[right - 1] != diff) {
                result += count_slices_(left, right, diff_count);
                ++left;
                diff = nums[right] - nums[left];
                diff_count = 0;
            } else {
                ++right;
                ++diff_count;
            }
        }

        result += count_slices_(left, right, diff_count);

        return result;
    }

private:
    int count_slices_(int left, int right, int diff_count) {
        return diff_count > 1 ? (right - left) * (right - left - 1) / 2 : 0;
    }
};

Search

Tags