早上发那题居然被点名了zzz血崩
题目地址：https://leetcode.com/problems/range-sum-query-immutable/?tab=Description
题意是大概求数组内部分和达到指定和，典型dp问题
用了暴力遍历，代码如下
后来看了一下别人solution，用了一个非常巧妙的办法
将每个元素因为可以用加或减法来求和，所以可以当作一个正数集和负数集相加。用P当做正数集，用F表示负数集，SUM表示所有数的和，T为所要达到的和值
有P-F=target因此有P-F + P+F = T + P+F，化简为2P＝T＋SUM，即P＝（T+SUM）／2。所以我们就是要求得一个正数集使得它们的和为一个定值，仔细一想，这不就将问题化为背包问题了吗？并且可以通过判断T＋SUM是否为偶数，否则肯定结果为0.下附上代码
网友评论