问题:
1.相似的题目一起做啊
2.看隐藏提示
3.多用用几种方法啊
正文:
class Solution {
public:
int pathSum(TreeNode* root, int sum) {
if(!root) return 0;
// 什么意思啊
// 前序遍历,深度优先
// 进行遍历全部节点
return numberOfPaths(root, sum) +
pathSum(root->left, sum) +
pathSum(root->right, sum);
}
private:
// 统计某一节点开始的路径个数
int numberOfPaths(TreeNode* root, int& sum){
if (!root) return 0;
int newsum = sum - root->val;
return (newsum == 0 ? 1 : 0) +
numberOfPaths(root->left, newsum) +
numberOfPaths(root->right, newsum);
}
};
560.subarray-sum-equals-k(超时!!!!)
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
if(!nums.size()) return 0;
return subarraySum(nums, 0, k);
}
private:
int subarraySum(vector<int>& nums,int i, int sum){
if(!nums.size() || i >= nums.size()) return 0;
return numOfPaths(nums, i, sum) + subarraySum(nums, i+1,sum);;
}
int numOfPaths(vector<int>& nums, int i, int sum){
if(!nums.size()||i >= nums.size()) return 0;
int new_sum = sum - nums[i];
return (new_sum == 0 ? 1 : 0) + numOfPaths(nums, i+1, new_sum);
}
};
437的神奇解法,好难。先放着。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
if(nums.empty()) return 0;
// 为什么要这么初始化呢?
// [1,1,1] 2
unordered_map<int, int> counts{{0, 1}};
int cur_sum = 0;
int ans = 0;
for(const int num : nums){
cur_sum += num;
// 对s[j] - s[i] == k 出现的个数进行计数 转换为对s[j]-k 的个数进行计数。
ans += counts[cur_sum - k];
// 把这个放在前面和后面又什么影响呢? [1] 0 会是错的。
++counts[cur_sum];
}
return ans;
}
};
网友评论