class Solution_Merge {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if ((nums1 == null || nums1.length == 0) && (nums2 == null || nums2.length == 0)) {
            return 0;
        }
        // 元素总个数：
        int sumLength = nums1.length + nums2.length;
        // 是否总共有偶数个元素，如果是，则需要累加中间的两个元素并除以二：
        boolean isEven = (sumLength % 2 == 0);
        // 中位数下标，如果共有奇数个则代表中位数本身，如果是偶数个则代表中间两个元素中下标更大的：
        int midIndex = sumLength / 2;
        // 用于记录两个数组分别归并到了第几位元素，也即接下来需要归并的第一位元素的下标：
        int index1 = 0, index2 = 0;
        // 用于记录实际中位数的值，注意因为精确到小数，所以要用 double：
        double midValue = 0;
        // 用于记录最新一个被归并的元素的值
        int value;
        // 只需要归并 midIndex + 1 次
        for (int i = 0; i <= midIndex; i++) {
            if (index1 >= nums1.length) {
                // 数组 1 越界说明已经被归并完了，则下一位被归并的就是从数组 2 取接下来的第 1 位元素
                value = nums2[index2++];
            } else if (index2 >= nums2.length) {
                // 数组 2 越界说明已经被归并完了，则下一位被归并的就是从数组 1 取接下来的第 1 位元素
                value = nums1[index1++];
            } else if (nums1[index1] > nums2[index2]) {
                // 否则如果数组 1 接下来一位比数组 2 接下来一位更小，则取数组 1 的接下来一位
                value = nums2[index2++];
            } else {
                // 否则如果数组 2 接下来一位比数组 1 接下来一位更小，则取数组 2 的接下来一位
                value = nums1[index1++];
            }
            // 如果共有偶数个元素，则中位数需要取中间两位，因此在 i == midIndex - 1 时先赋值，
            // 否则不处理相当于先赋了默认值 0。
            if (isEven && i == midIndex - 1) {
                midValue = value;
            }
            // 不论共有奇数个还是偶数个，都需要加上 midIndex 元素的值，为了兼容两种情况所以使用累加
            if (i == midIndex) {
                midValue += value;
            }
        }
        // 此时如果共有奇数个，则 midValue 就是最终中位数，否则 midValue 等于中间两个数的和，
        // 所以如果是偶数个，还需要除以二：
        if (isEven) {
            midValue /= 2.0d;
        }
        return midValue;
    }
}

class Solution_DoubleLoop {
    public int[] twoSum(int[] nums, int target) {
        int i = 0, j = 0;
        // 定义外层循环名
        outer:
        for (i = 0; i < nums.length - 1; i++) {
            // 题目给出了 2 <= nums.length <= 10^4，所以不用判断 j = i + 1 是否越界
            for (j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    // 找到了，直接跳出外层循环
                    break outer;
                }
            }
        }
        return new int[] {i, j};
    }
}

class Solution_MapHash {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int index = 0; index < nums.length; index++) {
            int diff = target - nums[index];
            if (map.containsKey(diff)) {
                return new int[] {index, map.get(diff)};
            }
            map.put(nums[index], index);
        }
        return new int[0];
    }
}