Skip to content

Latest commit

 

History

History
302 lines (237 loc) · 8.14 KB

README_EN.md

File metadata and controls

302 lines (237 loc) · 8.14 KB
comments difficulty edit_url tags
true
Medium
Array
Two Pointers
Dynamic Programming

3284. Sum of Consecutive Subarrays 🔒

中文文档

Description

We call an array arr of length n consecutive if one of the following holds:

  • arr[i] - arr[i - 1] == 1 for all 1 <= i < n.
  • arr[i] - arr[i - 1] == -1 for all 1 <= i < n.

The value of an array is the sum of its elements.

For example, [3, 4, 5] is a consecutive array of value 12 and [9, 8] is another of value 17. While [3, 4, 3] and [8, 6] are not consecutive.

Given an array of integers nums, return the sum of the values of all consecutive subarrays.

Since the answer may be very large, return it modulo 109 + 7.

Note that an array of length 1 is also considered consecutive.

 

Example 1:

Input: nums = [1,2,3]

Output: 20

Explanation:

The consecutive subarrays are: [1], [2], [3], [1, 2], [2, 3], [1, 2, 3].
Sum of their values would be: 1 + 2 + 3 + 3 + 5 + 6 = 20.

Example 2:

Input: nums = [1,3,5,7]

Output: 16

Explanation:

The consecutive subarrays are: [1], [3], [5], [7].
Sum of their values would be: 1 + 3 + 5 + 7 = 16.

Example 3:

Input: nums = [7,6,1,2]

Output: 32

Explanation:

The consecutive subarrays are: [7], [6], [1], [2], [7, 6], [1, 2].
Sum of their values would be: 7 + 6 + 1 + 2 + 13 + 3 = 32.

 

Constraints:

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

Solutions

Solution 1: Recurrence

We define two variables $f$ and $g$, representing the length of the increasing subarray ending at the current element and the length of the decreasing subarray ending at the current element, respectively. We use two other variables $s$ and $t$ to represent the sum of the increasing subarray ending at the current element and the sum of the decreasing subarray ending at the current element, respectively. Initially, $f = g = 1$, and $s = t = \textit{nums}[0]$.

Next, we traverse the array starting from the second element. For the current element $\textit{nums}[i]$, we consider the increasing subarray and the decreasing subarray ending at $\textit{nums}[i]$.

If $\textit{nums}[i] - \textit{nums}[i - 1] = 1$, then $\textit{nums}[i]$ can be added to the increasing subarray ending at $\textit{nums}[i - 1]$. In this case, we update $f$ and $s$, and add $s$ to the answer.

If $\textit{nums}[i] - \textit{nums}[i - 1] = -1$, then $\textit{nums}[i]$ can be added to the decreasing subarray ending at $\textit{nums}[i - 1]$. In this case, we update $g$ and $t$, and add $t$ to the answer.

Otherwise, $\textit{nums}[i]$ cannot be added to the increasing or decreasing subarray ending at $\textit{nums}[i - 1]$. We add $\textit{nums}[i]$ to the answer.

After the traversal, return the answer.

The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.

Python3

class Solution:
    def getSum(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        f = g = 1
        s = t = nums[0]
        ans = nums[0]
        for x, y in pairwise(nums):
            if y - x == 1:
                f += 1
                s += f * y
                ans = (ans + s) % mod
            else:
                f = 1
                s = y
            if y - x == -1:
                g += 1
                t += g * y
                ans = (ans + t) % mod
            else:
                g = 1
                t = y
            if abs(y - x) != 1:
                ans = (ans + y) % mod
        return ans

Java

class Solution {
    public int getSum(int[] nums) {
        final int mod = (int) 1e9 + 7;
        long s = nums[0], t = nums[0], ans = nums[0];
        int f = 1, g = 1;
        for (int i = 1; i < nums.length; ++i) {
            int x = nums[i - 1], y = nums[i];
            if (y - x == 1) {
                ++f;
                s += 1L * f * y;
                ans = (ans + s) % mod;
            } else {
                f = 1;
                s = y;
            }
            if (y - x == -1) {
                ++g;
                t += 1L * g * y;
                ans = (ans + t) % mod;
            } else {
                g = 1;
                t = y;
            }
            if (Math.abs(y - x) != 1) {
                ans = (ans + y) % mod;
            }
        }
        return (int) ans;
    }
}

C++

class Solution {
public:
    int getSum(vector<int>& nums) {
        const int mod = 1e9 + 7;
        long long s = nums[0], t = nums[0], ans = nums[0];
        int f = 1, g = 1;
        for (int i = 1; i < nums.size(); ++i) {
            int x = nums[i - 1], y = nums[i];
            if (y - x == 1) {
                ++f;
                s += 1LL * f * y;
                ans = (ans + s) % mod;
            } else {
                f = 1;
                s = y;
            }
            if (y - x == -1) {
                ++g;
                t += 1LL * g * y;
                ans = (ans + t) % mod;
            } else {
                g = 1;
                t = y;
            }
            if (abs(y - x) != 1) {
                ans = (ans + y) % mod;
            }
        }
        return ans;
    }
};

Go

func getSum(nums []int) int {
	const mod int = 1e9 + 7
	f, g := 1, 1
	s, t := nums[0], nums[0]
	ans := nums[0]

	for i := 1; i < len(nums); i++ {
		x, y := nums[i-1], nums[i]

		if y-x == 1 {
			f++
			s += f * y
			ans = (ans + s) % mod
		} else {
			f = 1
			s = y
		}

		if y-x == -1 {
			g++
			t += g * y
			ans = (ans + t) % mod
		} else {
			g = 1
			t = y
		}

		if abs(y-x) != 1 {
			ans = (ans + y) % mod
		}
	}

	return ans
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

TypeScript

function getSum(nums: number[]): number {
    const mod = 10 ** 9 + 7;
    let f = 1,
        g = 1;
    let s = nums[0],
        t = nums[0];
    let ans = nums[0];

    for (let i = 1; i < nums.length; i++) {
        const x = nums[i - 1];
        const y = nums[i];

        if (y - x === 1) {
            f++;
            s += f * y;
            ans = (ans + s) % mod;
        } else {
            f = 1;
            s = y;
        }

        if (y - x === -1) {
            g++;
            t += g * y;
            ans = (ans + t) % mod;
        } else {
            g = 1;
            t = y;
        }

        if (Math.abs(y - x) !== 1) {
            ans = (ans + y) % mod;
        }
    }

    return ans;
}