首页 > 其他分享 >LCR 012. 寻找数组的中心下标(简单)(主站724)

LCR 012. 寻找数组的中心下标(简单)(主站724)

时间:2024-11-13 10:20:08浏览次数:3  
标签:下标 nums int 主站 012 数组 LCR total sum

https://leetcode.cn/problems/tvdfij/
https://leetcode.cn/problems/find-pivot-index/
难度:☆☆☆

题目:

给你一个整数数组nums,请计算数组的中心下标 。数组中心下标是数组的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和。如果中心下标位于数组最左端,那么左侧数之和视为0,因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。如果数组有多个中心下标,应该返回最靠近左边的那一个。如果数组不存在中心下标,返回-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 ,二者相等。

输入:nums = [1, 2, 3]
输出:-1
解释:数组中不存在满足此条件的中心下标。

输入:nums = [2, 1, -1]
输出:0
解释:中心下标是 0 。
左侧数之和 sum = 0 ,(下标 0 左侧不存在元素),
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。

方法:数组,前缀和

设数组全部元素之和为total,中心元素为nums[i],其左边之和为sumleft,其右边之后为sumright。
total = sumleft + nums[i] + sumright,而sumleft = sumright,那么2 * sumleft + nums[i] = total。

Python
时间复杂度:O(n),其中n是nums的长度。
空间复杂度:O(1)。

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        total = sum(nums)
        for k, v in enumerate(nums):
            if sum(nums[:k]) * 2 + nums[k] == total:
                return k
        return -1

Java
时间复杂度:O(n),其中n是nums的长度。
空间复杂度:O(1)。

class Solution {
    public int pivotIndex(int[] nums) {
        int total = Arrays.stream(nums).sum();
        int sums = 0;
        for (int i = 0; i < nums.length; i++) {
            if (2 * sums + nums[i] == total) {
                return i;
            }
            sums += nums[i];
        }
        return -1;
    }
}

标签:下标,nums,int,主站,012,数组,LCR,total,sum
From: https://blog.csdn.net/weixin_43606146/article/details/143732163

相关文章

  • LCR 011. 连续数组(中等)(主站525)
    https://leetcode.cn/problems/A1NYOS/https://leetcode.cn/problems/contiguous-array/难度:☆☆☆☆题目:给定一个二进制数组nums,找到含有相同数量的0和1的最长连续子数组,并返回该子数组的长度。示例:输入:nums=[0,1]输出:2说明:[0,1]是具有相同数......
  • [luoguP2573/SCOI2012]滑雪
    题意给定一个有\(n\)个景点和\(m\)条边的无向图,景点有高度\(h_i\)。从景点\(i\)到\(j\)的移动仅当\(h_i\geqh_j\)且有边\((i,j)\)。从景点\(1\)出发,使用最短距离访问最多景点,且可使用回溯道具回到上一个点。求最多景点数和最短距离。sol如果本题无高度限制,那......
  • AT_agc012_f [AGC012F] Prefix Median 题解
    首先将序列排序,这是显然的。考虑倒着确定\(b\)序列中的每个数。即从完整的\(a\)序列开始,每次删掉两个数,记录中位数。先找出\(b\)序列合法的条件。容易发现对于所有\(i\),在\(b_{p_i}\)成为中位数时,\(p_i,p_{i+1}\)之间的所有数都已经被删除了,且\(i\lep_i\le2n-i\)。......
  • [NOIP2012 提高组] 国王游戏 题解
    [NOIP2012提高组]国王游戏典贪心。设当前点为\(i\),\(\prod_{k=0}^{i-1}a_k\)为\(x\),则对于\(i,j\)两点的答案:(为了方便,记\(i+1=j\))\[\mathit{res}_1=\max\bigg(\dfracx{b_i},\dfrac{xa_i}{b_j}\bigg)~;\]若交换,则:\[\mathit{res}_2=\max\bigg(\dfracx{b_j},\dfrac{......
  • 20241012 模拟赛
    20241012模拟赛A.组合一眼转化成前缀相减的形式,然后注意到\(a,b,c\le2000\),于是\(O(n^2)\)预处理就做完了。B.原神先考虑暴力一点的想法。考虑枚举最靠右的瓶子\(i\),再枚举选的瓶子的个数\(k\),那么这时无论在前面选了哪些数,答案都会异或上\(\sum_{j=i-k+1}^{i}a_j\)......
  • LeetCode LCR135[报数]
    题目链接LeetCodeLCR135[报数]详情实例题解思路通过pow函数对10进行幂运算,来获取报数范围然后循环遍历通过push_back方法将数字加入到容器内代码classSolution{public:vector<int>countNumbers(intcnt){vector<int>iRetVec;......
  • P4621 [COCI2012-2013#6] BAKTERIJE 题解
    一道很好的数学题。首先不难想到每个细菌的移动路线是有循环节的,循环节外的时间最多就是每个格子的四个方向都走一遍,也就是\(4\timesN\timesM\)。可以预处理每个细菌分别通过四个方向第一次到达终点的时间\(b_{i,0/1/2/3}\)和再次回到当前状态的循环节长度\(md_{i,0/1/2/......
  • AI预测福彩3D采取888=3策略+和值012路+胆码+通杀1码预测11月6日新模型预测第132弹
             经过100多期的测试,当然有很多彩友也一直在观察我每天发的预测结果,得到了一个非常有价值的信息,那就是9码定位的命中率非常高,100多期一共只错了12次,这给喜欢打私房菜的朋友提供了极高价值的预测结果~当然了,大部分菜友还是走的正常渠道,因此,得想办法进行缩水,尽......
  • AI预测体彩排3采取888=3策略+和值012路+胆码+通杀1码测试11月6日升级新模型预测第126
             经过100多期的测试,当然有很多彩友也一直在观察我每天发的预测结果,得到了一个非常有价值的信息,那就是9码定位的命中率非常高,已到达90%的命中率,这给喜欢打私菜的朋友提供了极高价值的预测结果~当然了,大部分菜友还是走的正常渠道,因此,得想办法进行缩水,尽可能少的......
  • leetcodeLCR 150. 彩灯装饰记录 II
    一棵圣诞树记作根节点为 root 的二叉树,节点值为该位置装饰彩灯的颜色编号。请按照从左到右的顺序返回每一层彩灯编号,每一层的结果记录于一行。示例1:输入:root=[8,17,21,18,null,null,6]输出:[[8],[17,21],[18,6]]提示:节点总数<=1000 /***Definitionfor......