设计网站排行榜前十名,注册工程师,安陆网站建设,徐州建站程序其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
2.1 前缀和的解题模板
2.1.1 最长递增子序列长度
2.1.2 寻找数组中第 k 大的元素
2.1.3 最长公共子序列… 其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
2.1 前缀和的解题模板
2.1.1 最长递增子序列长度
2.1.2 寻找数组中第 k 大的元素
2.1.3 最长公共子序列长度
2.1.4 寻找数组中第 k 小的元素
2.2 方法一前缀和
三、代码
3.2 方法一前缀和
四、复杂度分析
4.2 方法一前缀和 前言
这是力扣的 724 题难度为简单解题方案有很多种本文讲解我认为最奇妙的一种。
这是一道非常经典的前缀和问题虽然看似简单但它却能让你深入理解前缀和的特点。 一、题目描述
给你一个整数数组 nums 请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端那么左侧数之和视为 0 因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标应该返回 最靠近左边 的那一个。如果数组不存在中心下标返回 -1 。
示例 1 输入nums [1, 7, 3, 6, 5, 6]
输出3
解释
中心下标是 3 。
左侧数之和 sum nums[0] nums[1] nums[2] 1 7 3 11
右侧数之和 sum nums[4] nums[5] 5 6 11 二者相等。示例 2 输入nums [1, 2, 3]
输出-1
解释
数组中不存在满足此条件的中心下标。 示例 3 输入nums [2, 1, -1]
输出0
解释
中心下标是 0 。
左侧数之和 sum 0 下标 0 左侧不存在元素
右侧数之和 sum nums[1] nums[2] 1 -1 0 。提示
1 nums.length 104-1000 nums[i] 1000 二、题解 2.1 前缀和的解题模板
前缀和算法是一种在处理数组或链表问题时常用的技巧它可以有效地减少重复计算提高算法的效率。下面是一些常见的使用前缀和算法的题目以及解题思路
2.1.1 最长递增子序列长度 题目描述给定一个无序数组求最长递增子序列的长度。 解题思路可以使用前缀和和单调栈来解决这个问题。首先遍历数组计算出前缀和。然后使用单调栈记录当前递增子序列的起始位置。遍历数组时如果当前元素大于前缀和说明可以扩展当前递增子序列将当前位置入栈。如果当前元素小于等于前缀和说明当前递增子序列已经结束弹出栈顶元素。最后栈中剩余的元素即为最长递增子序列的起始位置计算长度即可。
2.1.2 寻找数组中第 k 大的元素 题目描述给定一个无序数组和一个整数k找到数组中第k大的元素。 解题思路可以使用前缀和和快速选择算法来解决这个问题。首先计算出数组的前缀和。然后使用快速选择算法在数组中找到第k小的元素。具体实现中每次选择一个枢轴元素将数组分成两部分小于枢轴的元素和大于枢轴的元素。如果枢轴左边的元素个数小于k则在左边的子数组中继续查找如果枢轴左边的元素个数大于等于k则在右边的子数组中继续查找。最后当找到第k小的元素时返回该元素即可。
2.1.3 最长公共子序列长度 题目描述给定两个字符串求最长公共子序列的长度。 解题思路可以使用动态规划算法来解决这个问题。如果字符串长度分别为m和n则可以定义一个二维数组dp[m1][n1]其中dp[i][j]表示字符串s1的前i个字符和字符串s2的前j个字符的最长公共子序列长度。根据动态规划的思想状态转移方程为dp[i][j] max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])。如果s1[i-1]等于s2[j-1]则dp[i][j] dp[i-1][j-1] 1否则dp[i][j]取其他两种情况中的较大值。最终结果为dp[m][n]。
2.1.4 寻找数组中第 k 小的元素 题目描述给定一个无序数组和一个整数k找到数组中第k小的元素。 解题思路可以使用前缀和和快速选择算法来解决这个问题。具体实现与寻找第k大元素类似只不过最后返回的是第k小的元素而非第k大的元素。
2.2 方法一前缀和
题目仅说明是整数数组无其他已知条件因此考虑直接遍历数组。 设索引 i 对应变量「左侧元素相加和 leftSum」和「右侧元素相加和 rightSum」。遍历数组 nums 每轮更新 leftSum 和 rightSum。遍历中遇到满足 leftSum rightSum 时说明当前索引为中心下标返回即可。若遍历完成仍未找到「中心下标」则返回 -1 。
初始化时相当于索引 i−1 此时 leftSum 0 , rightSum 所有元素的和 。 需要考虑大数越界问题。题目给定整数数组 nums 并给定取值范围。 题目的范围在 int 类型的取值范围内因此 sum_left 和 sum_right 使用 int 类型即可。 三、代码
3.2 方法一前缀和
Java版本
class Solution {public int pivotIndex(int[] nums) {int leftSum 0, rightSum Arrays.stream(nums).sum();for (int i 0; i nums.length; i) {rightSum - nums[i];if (leftSum rightSum) return i;leftSum nums[i];}return -1;}
}
C版本
class Solution {
public:int pivotIndex(vectorint nums) {int leftSum 0, rightSum accumulate(nums.begin(), nums.end(), 0);for (int i 0; i nums.size(); i) {rightSum - nums[i];if (leftSum rightSum) return i;leftSum nums[i];}return -1;}
};Python版本
class Solution:def pivotIndex(self, nums: List[int]) - int:left_sum, right_sum 0, sum(nums)for i in range(len(nums)):right_sum - nums[i]if left_sum right_sum:return ileft_sum nums[i]return -1Go版本
package mainfunc pivotIndex(nums []int) int {leftSum : 0rightSum : 0for _, v : range nums {rightSum v}for i, v : range nums {rightSum - vif leftSum rightSum {return i}leftSum v}return -1
}四、复杂度分析
4.2 方法一前缀和
时间复杂度 O(N) 其中 N 为数组 nums 长度。求和操作使用 O(N) 线性时间遍历 nums 最差使用 O(N) 线性时间。空间复杂度 O(1) 变量 leftSum , rightSum 使用常数大小空间。
