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<int>& 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