leetcode

problem1

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target的那两个整数，并返回它们的数组下标。

暴力枚举

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

哈希表

package problem1;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

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

    public static void main(String[] args) {

        int[] res = twoSum(new int[]{3, 8, 4, 6}, 7);

        System.out.println(Arrays.toString(res));
    }
}

时间复杂度

对数阶 $O(\log n)$

/* 对数阶（循环实现） */
int logarithmic(float n) {
    int count = 0;
    while (n > 1) {
        n = n / 2;
        count++;
    }
    return count;
}

问题规模为n,操作数为x

$$
2^x=n\ \Rightarrow
x=\log_{2}{n}
$$

空间复杂度

算法相关空间

算法运行中，使用的内存空间主要有以下几种：

「输入空间」用于存储算法的输入数据；
「暂存空间」用于存储算法运行中的变量、对象、函数上下文等数据；
「输出空间」用于存储算法的输出数据；

通常情况下，空间复杂度统计范围是「暂存空间」+「输出空间」。

暂存空间可分为三个部分：

「暂存数据」用于保存算法运行中的各种常量、变量、对象等。
「栈帧空间」用于保存调用函数的上下文数据。系统每次调用函数都会在栈的顶部创建一个栈帧，函数返回时，栈帧空间会被释放。
「指令空间」用于保存编译后的程序指令，在实际统计中一般忽略不计。