Java 练习

和为k的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。

方法一 枚举

我们可以枚举[0…i]里的所有的下标j来判断其中符合条件的数字。
所以，使用一个外层循环 for(int i = 0; i < nums.length; ++i) 来遍历数组 nums 中的每一个元素作为子数组的起始点。
对于每一个起始点 i，使用一个内层循环 for(int j = i; j >= 0; --j) 来遍历从 i 到数组起始位置（包括）的所有元素，计算这些元素组成的子数组的和 sum。
在内层循环中，每次将当前元素 nums[j] 加到 sum 上，然后检查 sum 是否等于 k。
如果等于k，count++，最后返回count，代表子数组的个数。

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        for(int i = 0;i < nums.length;++i){
            int sum = 0;
            for(int j = i;j >= 0; --j){
                sum += nums[j];
                if(sum == k){
                    count++;
                }
            }
        }
        return count;
    }
}

方法二 前缀和+哈希表

我们定义pre[i]为[0…i]中所有数的和，所以有: pre[i]=pre[i-1]+nums[i]
已知我们要找到[j…i]这个子数组和为k，所以有: pre[i] - pre[j-1] == k
所以，可以推导出: pre[j-1] = pre[i] - k
所以，我们只需要考虑以 i 结尾的和为 k 的连续子数组个数时只要统计有多少个前缀和为 pre[i]−k 的 pre[j] 即可。
即 mp.containsKey(pre - k)

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0, pre = 0;
        HashMap < Integer, Integer > mp = new HashMap < > ();
        mp.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            if (mp.containsKey(pre - k)) {
                count += mp.get(pre - k);
            }
            mp.put(pre, mp.getOrDefault(pre, 0) + 1);
        }
        return count;
    }
}

将有序数组转化为二叉搜索树

我们可以选择中间数字作为二叉搜索树的根节点，这样分给左右子树的数字个数相同或只相差 1，可以使得树保持平衡。如果数组长度是奇数，则根节点的选择是唯一的，如果数组长度是偶数，则可以选择中间位置左边的数字作为根节点或者选择中间位置右边的数字作为根节点，选择不同的数字作为根节点则创建的平衡二叉搜索树也是不同的。
所以，选择任意一个中间位置数字作为根节点，则根节点的下标为 mid=(left+right)/2 和 mid=(left+right+1)/2 两者中随机选择一个。

class Solution {
    Random rand = new Random();

    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }

    public TreeNode helper(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }

        int mid = (left + right + rand.nextInt(2)) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, left, mid - 1);
        root.right = helper(nums, mid + 1, right);
        return root;
    }
}