ARTS打卡：第十一周

每周完成一个ARTS：

Algorithm：每周至少做一个 leetcode 的算法题

Review：阅读并点评至少一篇英文技术文章

Tip：学习至少一个技术技巧

Share：分享一篇有观点和思考的技术文章

Algorithm

1. Two Sum(Easy)

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

@DevDocsleetcode.com/problems/two-sum

大致题意：
给一个整形数组，返回两个数组下标，两个数组下标对应的值相加，要等于目标值。
你可以假设每一个输入的数组，只有一种答案，并且你不能使用同一个元素两次。

这种题目，一眼看上去，是可以用暴力破解的，不过暴力破解虽然能解决问题，但我们这种三好青年，是有追求，有梦想的，用最少的时间和空间去解决问题，才是我们的终极目标。

解题思路一：暴力破解，双重遍历
这种解法就简单直接了，双重循环遍历即可。

代码如下：

/**
 * 暴力破解，双重遍历
 *
 * @param nums   输入数组
 * @param target 目标值
 * @return 
 */
public static int[] twoSum1(int[] nums, int target) {
    if (nums.length < 1) {
        throw new IllegalArgumentException("No two sum solution");
    }
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

结果：
Runtime: 18 ms, faster than 38.89% of Java online submissions for Two Sum.
Memory Usage: 38.2 MB, less than 94.24% of Java online submissions for Two Sum.

从结果上看，我们还是有很大优化空间的。

复杂度分析：
时间复杂度：O(n²)
空间复杂度：O(1)

解题思路二：借助哈希表，空间换时间，优化遍历
可以利用哈希表的特性，减少遍历次数，详细实现不难，直接看代码即可。

代码如下：

/**
 * 借助哈希表进行优化
 *
 * @param nums   输入数组
 * @param target 目标值
 * @return
 */
public static int[] twoSum(int[] nums, int target) {
    // 边界条件
    if (nums.length < 1) {
        throw new IllegalArgumentException("No two sum solution");
    }
    // 创建一个 HashMap，key 为数组的值，value 为值对应的数组下标
    // 用于记录遍历过的数组的值与下标，便于快速查找到所需的值
    Map<Integer, Integer> hash = new HashMap<>(16);
    // 循环遍历数组
    for (int i = 0; i < nums.length; i++) {
        // 我们的目的是找到符合 nums[i] + nums[j] = target 的 i 和 j，t 就是 nums[j]
        int t = target - nums[i];
        // 查看 t 是否在已访问过的数组值内 即哈希表的 keys 包不包含 t，
        // 加上由于题目要求同一个元素不能使用两次，所以还需满足当前下标 i 不能与 hash.get(t) 的值一致
        // 即 hash.containsKey(t) && hash.get(t) != i
        if (hash.containsKey(t) && hash.get(t) != i) {
            return new int[]{hash.get(t), i};
        }
        // 记录已访问过的，数组的值与下标
        hash.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

结果：
Runtime: 2 ms, faster than 99.20% of Java online submissions for Two Sum.
Memory Usage: 37.4 MB, less than 99.67% of Java online submissions for Two Sum.

复杂度分析：
时间复杂度：O(n)
空间复杂度：O(n)

Review

本周阅读是：《Top 10 Mistakes Java Developers Make》。

作者在文中总结了 Java 开发人员经常犯的十大错误：

Convert Array to ArrayList（Array 转 ArrayList）
Check If an Array Contains a Value（检查数组是否包含某个值）
Remove an Element from a List Inside a Loop（从 List 的循环中删除 List 的元素）
Hashtable vs HashMap
Use Raw Type of Collection（使用原始类型的集合）
Access Level（访问级别）
ArrayList vs. LinkedList
Mutable vs. Immutable（可变与不可变）
Constructor of Super and Sub（父类和子类的构造函数）
“” or Constructor?（””或构造函数）

作者在文中对每点错误都进行了详细的分析，并给出了对应的解决方案或说明。
文中的英语其实不难理解，感兴趣的小伙伴们，可以通过原文了解更多的详情。
如果实在不想看英语，那可以看看这篇译文：Java开发人员最常犯的10个错误。

Tip

本周分享：Apache JMeter 的使用入门。

本周分享猪猪大佬的公众号-工匠人生中的一篇文章：《如何将长URL转换为短URL？》
通过这篇文章，我们可以了解到：

如何将长URL生成短URL
短地址从URL输入到页面展现到底发生了什么？
短连接的设计思路
发号器的设计思路
知乎关于生成短地址的讨论

这里摘取文中提到的，一部分参考文章的地址：