对于算法中求 xxx 出现次数题型的解法的一个疑问

[yongzhong]

算法题中有些求出现次数的题通常可以通过其中的值计算出来(而非条件成立后+=1 这样的方式),原理为何?

可能描述的不太清楚,举个例子
https://leetcode.com/problems/path-sum-iii/这道题的这一解法
https://discuss.leetcode.com/topic/64526/17-ms-o-n-java-prefix-sum-method

中的 res,通过一些运算就得到了最终的答案
以前也遇到过类似的题型,总是不太理解

[akking]

我觉得你想问的是 backtracking 的原理吧？
凭空想的确挺难的， 多做题就好了

[zhy0216]

@akking 这题没有用到 backtracking 吧?

我比较喜欢这个答案 https://discuss.leetcode.com/topic/69803/easy-to-understand-python-code

[yongzhong]

@zhy0216 这个解法看上去比较清晰,但仍然不是最优解,耗时达到了 200 多 ms.而且这个解法的思路也还是通过 result.count(sum)去判断是否相等,和上面提到的那个解法不太一样

[zhy0216]

我觉得是一样, 我改了下代码, 逻辑是一致的, 就是从数组->dict:

```python
def helper(self, root, sum):
from collections import defaultdict
if not root: return None

result = defaultdict(int)
result[root.val] += 1


left, right = self.helper(root.left, sum), self.helper(root.right, sum)

if left:
for key in left:
result[key+root.val] += left[key]
if right:
for key in right:
result[key+root.val] += right[key]

self.count += result[sum]

return result
```

不过不知怎么, 速度更慢了

[zhy0216]

上面的结构不好~~
http://pastebin.com/t8iTe6WB

[akking]

@zhy0216 为什么不是？ DFS 加上返回时删除这一步的计算结果。典型的 backtrack 。