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

相关文章

来自专栏一个会写诗的程序员的博客

Kotlin 中的集合类排序Kotlin 开发者社区

Kotlin使用扩展方法构建在Java Collection框架之上。这大大提高了可用性和可读性,而无需第三方依赖,如Apache Commons或Guava。

1375
来自专栏lgp20151222

java 核心技术 读后总结

如 AbcController和AbcService两个文件,javac Abc*.java 即可一次性编译两个

672
来自专栏哲学驱动设计

重构一个繁琐的数据结构

    在GIX4项目的开发过程中,遇到一个比较复杂的数据结构。复杂,是因为它有许多限制条件。我的工作是在现有系统中,添加新的功能,并在过程中重构部分旧代码。 ...

22410
来自专栏jeremy的技术点滴

写py2、py3兼容的代码

8198
来自专栏Python小屋

Python花式编程案例锦集(1)

首先解答上一篇文章详解Python中的序列解包(2)中最后的习题,该题答案为5,表达式功能为迭代求解序列中元素的最大值。 -----------------分割...

3735
来自专栏小樱的经验随笔

POJ 1804 Brainman(5种解法,好题,【暴力】,【归并排序】,【线段树单点更新】,【树状数组】,【平衡树】)

Brainman Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 1057...

4047
来自专栏海纳周报

Python的三个问题

第一,以下程序的执行结果是什么? def foo(a = []): a.append(1) print a foo()foo() 第二,以下...

2797
来自专栏晓晨的专栏

C#自动识别文件编码

2303
来自专栏华仔的技术笔记

再议Block

2947
来自专栏Python小屋

Python函数中单独一个星号或斜线作为形参的含义

在函数定义时,位于*parameter或单独一个星号*之后的所有参数都只能以关键参数的形式进行传值,不接收其他任何形式的传值。 >>> def demo(a, ...

3576

扫码关注云+社区