前缀和一＞寻找数组的中心下标

用户11305962

发布于 2024-10-17 08:17:29

940

发布于 2024-10-17 08:17:29

文章被收录于专栏：学习

1.题目：

2.解析：

如果暴力解法时间复杂度是O(N^2)，定个，i，遍历左边右边；这里可以优化为前缀和的做法，其实就是个动态规划。

代码：

public int pivotIndex(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];

        //预处理前缀和数组
        for(int i = 1; i < n; i++)
          f[i] = f[i-1] + nums[i-1];

        for(int i = n-2; i >= 0; i--)
          g[i] = g[i+1] + nums[i+1];  

        //使用前缀和数组
        for(int i = 0; i < n; i++)
          if(f[i] == g[i]) return i;

        return -1;  
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-10-17，如有侵权请联系 cloudcommunity@tencent.com 删除

int