LeetCode-724-寻找数组的中心索引

2023-10-08 00:58

本文主要是介绍LeetCode-724-寻找数组的中心索引,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 题目要求
  • 题目示例
  • 题解
  • 源代码
  • 官方题解--前缀和法

题目要求

给定一个整数类型的数组 nums,请编写一个能够返回数组 “中心索引” 的方法。
中心索引:数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。
如果数组不存在中心索引,那么应该返回 -1。如果数组有多个中心索引,那么应该返回最靠近左边的那一个。

题目示例

输入:
nums = [1, 7, 3, 6, 5, 6]
输出:3
输入:
nums = [1, 2, 3]
输出:-1

题解

采用的比较暴力的方法,左右累加判断相等;为了防止首尾为0的情况,声明了一个新的数组使数组的首尾元素为0,中间元素为原来的元素。

源代码

class Solution {public int pivotIndex(int[] nums) {int[] tmp = new int[nums.length + 2];for(int k=1;k<nums.length + 1;k++){tmp[k] = nums[k - 1];}int left=0,right=0;for(int i=0;i<tmp.length;i++){right = 0;left += tmp[i];for(int j=tmp.length-1;j> i;j--){right += tmp[j];if(left == right && i == j - 2)return i;}}return -1;}
}

在这里插入图片描述

官方题解–前缀和法

S 是数组的和,当索引 i 是中心索引时,位于 i 左边数组元素的和 leftsum 满足 S - nums[i] - leftsum。
只需要判断当前索引 i 是否满足 leftsum==S-nums[i]-leftsum 并动态计算 leftsum 的值

class Solution {public int pivotIndex(int[] nums) {int sum = 0, leftsum = 0;for (int x: nums) sum += x;for (int i = 0; i < nums.length; ++i) {if (leftsum == sum - leftsum - nums[i]) return i;leftsum += nums[i];}return -1;}
}

在这里插入图片描述

这篇关于LeetCode-724-寻找数组的中心索引的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/161611

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

跨国公司撤出在华研发中心的启示:中国IT产业的挑战与机遇

近日,IBM中国宣布撤出在华的两大研发中心,这一决定在IT行业引发了广泛的讨论和关注。跨国公司在华研发中心的撤出,不仅对众多IT从业者的职业发展带来了直接的冲击,也引发了人们对全球化背景下中国IT产业竞争力和未来发展方向的深思。面对这一突如其来的变化,我们应如何看待跨国公司的决策?中国IT人才又该如何应对?中国IT产业将何去何从?本文将围绕这些问题展开探讨。 跨国公司撤出的背景与

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题,本文将一起从代码层去分析为什么没有建立索引? 开源ERP项目地址:https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

寻找身高相近的小朋友

题目描述: 小明今年升学到小学一年级,来到新班级后发现其他小朋友们身高参差不齐,然后就想基于各小朋友和自己的身高差对他们进行排序,请帮他实现排序。 输入描述: 第一行为正整数H和N,0<H<200,为小明的身高,0<N<50,为新班级其他小朋友个数。第二行为N个正整数H1-HN,分别是其他小朋友的身高,取值范围0<Hi<200(1<=i<=N),且N个正整数各不相同。 输出描述: 输出

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点