Skip to content

Latest commit

 

History

History
304 lines (237 loc) · 8.02 KB

README.md

File metadata and controls

304 lines (237 loc) · 8.02 KB
comments difficulty edit_url tags
true
中等
数组
双指针
动态规划

3284. 连续子数组的和 🔒

English Version

题目描述

如果一个长度为 n 的数组 arr 符合下面其中一个条件，可以称它 连续：

  • 对于所有的 1 <= i < n，arr[i] - arr[i - 1] == 1。
  • 对于所有的 1 <= i < n，arr[i] - arr[i - 1] == -1。

数组的 值 是其元素的和。

例如，[3, 4, 5] 是一个值为 12 的连续数组，并且 [9, 8] 是另一个值为 17 的连续数组。而 [3, 4, 3] 和 [8, 6] 都不连续。

给定一个整数数组 nums，返回所有 连续 子数组 的 值 之和。

由于答案可能很大，返回它对 109 + 7 取模 的值。

注意 长度为 1 的数组也被认为是连续的。

 

示例 1：

输入：nums = [1,2,3]

输出：20

解释：

连续子数组为：[1]，[2]，[3]，[1, 2]，[2, 3]，[1, 2, 3]。
它们的值之和为：1 + 2 + 3 + 3 + 5 + 6 = 20。

示例 2：

输入：nums = [1,3,5,7]

输出：16

解释：

连续子数组为：[1]，[3]，[5]，[7]。
它们的值之和为：1 + 3 + 5 + 7 = 16。

示例 3：

输入：nums = [7,6,1,2]

输出：32

解释：

连续子数组为：[7]，[6]，[1]，[2]，[7, 6]，[1, 2]。
它们的值之和为 7 + 6 + 1 + 2 + 13 + 3 = 32。

 

Constraints:

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

解法

方法一：递推

我们定义两个变量 $f$ 和 $g$，分别表示以当前元素结尾的递增子数组的长度和以当前元素结尾的递减子数组的长度，用另外两个变量 $s$ 和 $t$ 分别表示以当前元素结尾的递增子数组的和和以当前元素结尾的递减子数组的和。初始时 $f = g = 1$，而 $s = t = \textit{nums}[0]$。

接下来，我们从第二个元素开始遍历数组，对于当前元素 $\textit{nums}[i]$，我们分别考虑以 $\textit{nums}[i]$ 结尾的递增子数组和递减子数组。

如果 $\textit{nums}[i] - \textit{nums}[i - 1] = 1$，那么 $\textit{nums}[i]$ 可以加入到以 $\textit{nums}[i - 1]$ 结尾的递增子数组中，此时我们更新 $f$ 和 $s$，并将 $s$ 加到答案中；

如果 $\textit{nums}[i] - \textit{nums}[i - 1] = -1$，那么 $\textit{nums}[i]$ 可以加入到以 $\textit{nums}[i - 1]$ 结尾的递减子数组中，此时我们更新 $g$ 和 $t$，并将 $t$ 加到答案中。

否则，$\textit{nums}[i]$ 无法加入到以 $\textit{nums}[i - 1]$ 结尾的递增子数组或递减子数组中，我们将 $\textit{nums}[i]$ 加到答案中。

遍历结束后，返回答案即可。

时间复杂度 $O(n)$，其中 $n$ 是数组的长度。空间复杂度 $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;
}