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 条评论
登录 后参与评论

相关文章

来自专栏debugeeker的专栏

《coredump问题原理探究》Linux x86版4.3节函数的逆向之条件结构

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

732
来自专栏性能与架构

JS闭包

JS的闭包用法给开发带来了极大的便利,它的使用方式非常自然,以至于很多同学并不很了解闭包,却可以在实际开发中顺畅的使用了 例如下面的代码,给button添加...

3264
来自专栏HTML5学堂

Javascript解析机制 执行机制

HTML5学堂:在学习JavaScript过程中,我们需要了解事件的机制是怎么执行的?本文将会提到JavaScript事件机制的解析,希望对大家有帮助! jav...

2674
来自专栏龙渊阁测试精英

Jmeter(三十)_TimeShift函数在JSR223中的使用

日期 - 这是日期值。用于如果要通过添加或减去特定天数,小时或分钟来创建特定日期的情况。如果参数值未通过,则使用当前日期。

753
来自专栏北京马哥教育

Python 开发者不得不知的魔术方法(Magic Method)

来源:j_hao104 my.oschina.net/jhao104/blog/779743 介绍 在Python中,所有以“__”双下划线包起来的方法,都统...

2647
来自专栏编程微刊

回调函数路由,模板渲染

1375
来自专栏Hongten

python开发_python中的Boolean运算和真假值

621
来自专栏前端知识分享

第219天:Angular---过滤器

 在Angular中,过滤器的功能主要是格式化数据表达式,且可以自定义过滤器。作用域(scope)主要服务于页面模板,在控制器和页面中起桥梁作用,保存模板中的数...

824
来自专栏海天一树

小朋友学Python(20):面向对象

一、类与对象 例1 class Employee: 'Base class of employee' empCount = 0 def __i...

3169
来自专栏每日一篇技术文章

Swift3.0 - 函数和闭包

需求: 创建一个接口,输入true 返回 两个数相加的函数,输入false 返回两个数相减的函数

713

扫码关注云+社区