LWC 58:724. Find Pivot Index

LWC 58:724. Find Pivot Index

传送门:724. Find Pivot Index

Problem:

Given an array of integers nums, write a method that returns the “pivot” index of this array. We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index. If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.

Example 1:

Input: nums = [1, 7, 3, 6, 5, 6] Output: 3 Explanation: The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3. Also, 3 is the first index where this occurs.

Example 2:

Input: nums = [1, 2, 3] Output: -1 Explanation: There is no index that satisfies the conditions in the problem statement.

Note:

The length of nums will be in the range [0, 10000].

Each element nums[i] will be an integer in the range [-1000, 1000].

思路: 判断当前坐标点的左侧元素之和是否和右侧元素之和相等,返回第一个符合情况的下标。

空间换时间,说白了,以O(1)的速度查询累加和,以O(n)的速度更新累加和数组即可,再以O(n)的速度搜索符合情况的下标。

代码如下:

    public int pivotIndex(int[] nums) {
        int n = nums.length;
        int[] lf = new int[n];
        int[] rt = new int[n];

        int sum = 0;
        for (int i = 0; i < n; ++i) {
             lf[i] = sum;
             sum += nums[i];
        }

        sum = 0;
        for (int j = n - 1; j >= 0; --j) {
            rt[j] = sum;
            sum += nums[j];
        }

        for (int i = 0; i < n; ++i) {
            if (lf[i] == rt[i]) {
                return i;
            }
        }

        return -1;
    }

累加和版本:

    public int pivotIndex(int[] nums) {
        int n = nums.length;
        int[] sums = new int[n + 1];

        for (int i = 0; i < n; ++i){
            sums[i + 1] = sums[i] + nums[i];
        }

        for (int i = 0; i < n; ++i){
            if (sums[i + 1] == sums[n] - sums[i]){
                return i;
            }
        }

        return -1;
    }       

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法与数据结构

CC150--基本字符串压缩

利用字符重复出现的次数,编写一个方法,实现基本的字符串压缩功能。比如,字符串“aabcccccaaa”经压缩会变成“a2b1c5a3”。若压缩后的字符串没有变短...

1163
来自专栏小狼的世界

两个有序数组中查找第K大数

题目:两个数组A、B,长度分别为m、n,即A(m)、B(n),分别是递增数组。求第K大的数字。

1102
来自专栏海天一树

小朋友学C语言(33):三目运算符

三目运算符(ternary operator),又称条件运算符、三元运算符,是计算机语言(c,c++,java等)的重要组成部分。它是唯一有3个操作数的运算符。...

2746
来自专栏Java帮帮-微信公众号-技术文章全总结

14(01)正则表达式,Pattern,Mactcher,Math,BigInteger,BigDeximal,System等

学正则表达式之前qq号问题: package cn.itcast_01; import java.util.Scanner; /* * 校验qq号码. * ...

2695
来自专栏十月梦想

php常用函数分类整理

一、数组操作的基本函数 数组的键名和值 array_values($arr);  获得数组的值 array_keys($arr);  获得数组的键名 array...

732
来自专栏Bingo的深度学习杂货店

Q69 Sqrt(x)

Implement int sqrt(int x). Compute and return the square root of x. x is guarant...

3247
来自专栏蓝天

编译错误:stray ‘\357’ in program的解决方法

如编译时遇到如下所示的编译错误: ./month_matcher.cpp:1: error: stray ‘\357’ in program ./mon...

681
来自专栏偏前端工程师的驿站

(cljs/run-at (JSVM. :browser) "简单类型可不简单啊~")

前言  每逢学习一个新的语言时总要先了解这门语言支持的数据类型,因为数据类型决定这门语言所针对的问题域,像Bash那样内置只支持字符串的脚步明显就是用于文本处理...

1847
来自专栏GreenLeaves

JavaScript引用类型之Object类型

在JavaScript中大多数的引用类型都是Object的实例,Object类型也是使用最多的类型! 创建Object类型实例的方式有两种,下面分别来分析一下:...

1955
来自专栏Jack-Cui

496. Next Greater Element I(Stack-Easy)

    You are given two arrays (without duplicates) nums1 and nums2 where nums1’s ...

1898

扫码关注云+社区