因昨天晚上有事，故本次更新推迟了一天。
Leetcode 543：二叉树的直径
题目描述
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
示例
给定二叉树
1
/ \
2 3
/ \
4 5 返回3，它的长度路径[4,2,1,3]或者[5,2,1,3]
解题思路
最长长度一定是最长左子树的长度+最长右子树的长度+1，按照这个思路来走即可。
代码实现
int ans;
int getDepth(TreeNode* root) {
if (root == nullptr)
return 0;
int ll = getDepth(root->left);
int rr = getDepth(root->right);
ans = max(ans, ll+rr+1);
return max(ll, rr) + 1;
}
int diameterOfBinaryTree(TreeNode* root) {
ans = 1;
getDepth(root);
return ans - 1;
}
代码性能
运行耗时：16ms
内存消耗：19.7MB
Leetcode 560：和为k的子数组
题目描述
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例
输入:nums = [1,1,1], k = 2。输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
解题思路
我感觉没啥需要写的，很简单就看懂。复杂度O(n2)有一点高。
代码实现
int subarraySum(vector& nums, int k) {
if (nums.empty())
return -1;
int count = 0;
for (int i = 0; i < nums.size(); i++)
{
int sum = 0;
for (int j = i;j < nums.size(); j++)
{
sum += nums[j];
if (sum == k)
count++;
}
}
return count;
}
代码性能
复杂度：O(n2)
执行用时：752ms
内存消耗：9.7MB