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

admin管理员组

文章数量:1794759

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

1.题目： 

---

2.解析： 

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

---

代码： 

代码语言：javascript代码运行次数：0运行复制

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 删除前往查看int遍历动态规划数组优化

本文标签： 前缀和一＞寻找数组的中心下标