虽说自己致力于搞客户端,但作为工程师的内功,算法能力必不可少,而且决定了日后的高度。拖拉许久,看了几篇文章之后,决定以 LeetCode 为平台,附以一些参考资料,边学边练。

做题的本质还是练习,一为透彻理解,二为保持状态。 LeetCode 现在有了中文版,名叫力扣,相比于牛客网等清爽很多,就做题而言功能已经很完善了,也带有比较纯粹的社交圈子。上面还有一些介绍基础知识的探索卡片,同样简洁,我就是从这里开始的。

这一道就是数组和字符串卡片的第一道习题。

题目

寻找数组的中心索引

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

来源:力扣(LeetCode),详见👇
链接:https://leetcode-cn.com/problems/find-pivot-index

解读

这道题应该是考察对于数组操作的理解。

题目很容易懂,中心索引就是个分界符,左右两边的数字之和相等,目标就是返回它的位置。如果没有返回 -1 ,如果多个返回第一个。

限制条件里给的用例都是整数,在可以正常运算的范围内,不需要考虑大数计算。

所以当成一个数学问题 + 数组操作即可解决。

基础方法

最直接的思维,从第一个数字开始遍历,计算前后数字的和,比较是否相等。

class Solution {
    public int pivotIndex(int[] nums) {
        int sumA = 0, sumB = 0;
        int res = -1;
        // 第一个遍历,当前待验证的索引
        for (int index = 0; index < nums.length ; ++index) {
            // 第二个遍历,计算前后的数字之和
            for (int i = 0; i < nums.length; ++i) {
                if (i < index) {
                    sumA += nums[i];
                }else if (i > index){
                    sumB += nums[i];
                }
            }
            if (sumA == sumB) {
                res = index;
                break;
            }else{
                sumA = 0;
                sumB = 0;
            }
        }
        return res;
    }
}

这个解法就是单纯的暴力计算了,没啥优化。因为嵌套了一个循环,所以时间复杂度为 O(n^2) 。

刚开始我把第二个遍历从下标 1 开始了,结果跑到一半失败,因为有个测试用例是这样 [0, 1, -1] ,应该返回的结果是 0 ,第一个元素左边是空的,当做和为 0 ,同样需要判断。

提交后结果如下,可见用时还是很长的:

基础

高级方法

也是看了一下别人的思考过程 =_= 大体上是做了这么个变换:

首先左边之和 + 右边之和 + 中心索引 = 整个数组之和

sumLeft + sumRight + index = sum

中心索引两边的数字之和不是相等吗,就有了

sumLeft = sumRight 

因此做个代换,就成了

2 * sumLeft =  sum - index

这样只需要先算一遍数组之和,然后再累加判断即可。虽然还是两次循环,但已经不用嵌套了,时间复杂度也就从 O(n^2) 降低到了 O(n) 。除此之外,针对数组长度为 0 和 1 的情况单独做了判断。根据定义,以及两端之外当做 0 的约定,显然结果分别为不存在和第一个,即 -1 和 0。

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

这样就快很多了,结果如下:

高级

最后这个击败数量好像有点奇怪,我看了下时间和空间上最优解的,变化不大,而且时间上最快 1ms 那个原样提交,得到的结果跟上面还是一样。可能是早先的测试用例有所不同吧,导致这个数据有问题。这个方法的解决程度应该足够了。

结语

如果不是科班出身,算法的基础能力比较薄弱(比如目前的我),最好还是多看些参考资料。这样理解起来会更加轻松,方法得当,效率才高嘛。这道题虽然难度 easy ,笨办法可解,但通过学习就能获得更好的思路,开拓视野。练习的目的也就达到了。

值得一提的是,现在网上找东西信息量严重溢出,容易一找就沉迷一下午,然后被各种大佬打击到。所以找的喜欢的就行了,赶紧干起来为妙,哈哈。

最后推荐一个非常平易近人,传递思维的Gitbook,作者是个暴躁成都老哥🤣写的蛮好: