前缀和

2024年3月9日美团笔试 前缀和 * 1

2024年3月13日 携程笔试 前缀和 * 1

练习题

2602、使数组元素全部相等的最少操作次数

image-20240313215122293

image-20240313215333584

image-20240313215347177

本题类似于携程的笔试题，暴力算法的时间复杂度为O(n²)，n=10^5，铁超时

1
2
3
4
5
6
7
8
9
10
class Solution:
    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:
        res = []

        for q in queries:
            operation = 0
            for i in range(len(nums)):
                operation += abs(nums[i]-q)
            res.append(operation)
        return res

image-20240313215259899

正确思路：

前缀和+二分查找

构造前缀和：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:
        n = len(nums)
        nums.sort()
        s = list(accumulate(nums, initial=0))  # 前缀和
        ans = []
        for q in queries:
            j = bisect_left(nums, q)
            # print(j)
            left = q * j - s[j]  # 蓝色面积
            right = s[n] - s[j] - q * (n - j)  # 绿色面积
            ans.append(left + right)
        return ans

image-20240313222304904

238、除以自身以外数组的乘积

303、区域和检索

image-20240522193620214

image-20240522193632228

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class NumArray:

    def __init__(self, nums: List[int]):
        s = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            s[i + 1] = s[i] + nums[i]
        self.s = s

    def sumRange(self, left: int, right: int) -> int:
        return self.s[right + 1] - self.s[left]


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(left,right)

560、和为K的子数组

image-20240522201658158

思路：

构造s数组，然后将每个位置的值设置为对应的前缀和，连续的子数组的和就为s[j]-s[i]

myhash存储的是对应元素出现的次数，例如和为1的子数组出现的次数

两次遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        myhash = defaultdict(int)
        s = [0] * (len(nums) + 1)
        for index, num in enumerate(nums):
            s[index + 1] = s[index] + num
        # print(s)
        # 连续的子数组之和为K  s[j]-s[i]=k
        # s[j]-s[i]=连续子数组和=k
        res = 0
        # 需要注意特殊情况 nums=[1],k=1的情况，如果s不设置s[0]就会出现结果为0的情况
        for ss in s:
            res += myhash[ss - k]
            myhash[ss] += 1
        return res

一次遍历：

一边计算前缀和，一边遍历前缀和

1
2
3
4
5
6
7
8
9
10
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        myhash = defaultdict(int)
        res = s = 0
        myhash[0] = 1
        for num in nums:
            s += num
            res += myhash[s - k]
            myhash[s] += 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        s = [0] * (len(nums) + 1)
        for index, num in enumerate(nums):
            s[index + 1] = s[index] + num
        # print(s) # [0,1,0,0]
        # 看差值是否在哈希表中 记录其出现的次数
        res = 0
        myhash = defaultdict(int)
        for ss in s:
            if ss - k in myhash:
                res += myhash[ss - k]
            myhash[ss] += 1

        return res