Leetcode——前缀和

分手后的思念是犯贱 2022-10-24 01:42 172阅读 0赞

[题目直通车][Link 1]

# 运用数学思想 #

左边的和 = 总和 - 当前索引的值-右边的和  
题目要求两边相等，也就是 左边的和 = 右边的和  
因此公式变成 左边的和 + 左边的和（右边的和） +当前索引的值 = 总和

class Solution:
        def pivotIndex(self, nums: List[int]) -> int:
            if not nums: return -1
            total = 0
            for j in range(len(nums)):
                total += nums[j]
            sum = 0
            for i in range(len(nums)):
                if( 2 * sum +nums[i] == total):return i
                sum += nums[i]
            return -1

# 运用双指针：因为如果两边相等，**左边的和 + nums\[i\] = 右边的和 +nums\[i\]**=>左边的和 = 右边的和 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70]  
![!\[在这里插入图片描述\](https://img-blog.csdnimg.cn/20210128211237303.png?x-oss-process=image/watermark,type\_ZmFuZ3poZW5naGVpdGk,shadow\_10,text\_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg==,size\_16,color\_FFFFFF,t\_70][https_img-blog.csdnimg.cn_20210128211237303.png_x-oss-process_image_watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70 2]

class Solution:
        def pivotIndex(self, nums: List[int]) -> int:
            if not nums: return -1
            leftsum = 0
            rightsum = 0
            for i in range(len(nums)):
                rightsum += nums[i]
            for i in range(len(nums)):
                leftsum +=nums[i]
                if leftsum == rightsum:
                    return i
                    break
                rightsum -= nums[i]
               
            return -1

[303][]  
这题要求某个区间的元素之和，立马想到 preSum 这个方法。它的计算方法是从左向右遍历数组，当遍历到数组的 i 位置时，preSum表示 i 位置左边的元素之和。也就是说如果要计算包括i位置的前缀和，就应该取preSum\[i+1\].  
题目是求i到j区间，可以理解就是j之前的左边数的和加上就本身减去i左边的数的总和。  
![在这里插入图片描述][20210302083955428.gif_pic_center]

class NumArray:
    
        def __init__(self, nums: List[int]):
            N = len(nums)
            self.preSum = [0]*(N+1)
            for i in range(N):
                self.preSum[i+1] = self.preSum[i]+nums[i]
    
        def sumRange(self, i: int, j: int) -> int:
            return self.preSum[j+1]-self.preSum[i]

[Link 1]: https://leetcode-cn.com/problems/find-pivot-index/solution/xun-zhao-shu-zu-de-zhong-xin-suo-yin-by-gzjle/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70]: /images/20221024/4ee55f6a0442474db705b31d73d48662.png
[https_img-blog.csdnimg.cn_20210128211237303.png_x-oss-process_image_watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70]: /images/20221024/781f0e0bb9144cccb8534565cca1ac4d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70 1]: /images/20221024/e57b42be8fca4892aca2ff970c32abf2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70 2]: /images/20221024/839a36c053c84403b600a835c5d5df99.png
[303]: https://leetcode-cn.com/problems/range-sum-query-immutable/submissions/
[20210302083955428.gif_pic_center]: /images/20221024/3d97e4145737442595fec44dc8e84f19.png