两数之和

本身是没有什么难度的题目，但是可以用于开拓思路。

解法1

没有技术含量，LeetCode上面没有对边界值和特殊情况做处理，比如

• nums数组中存在重复数据
• nums数组元素小于2的情况

 public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        // 确保数组长度要大于等于2
        if (nums.length < 2)
            return new int[]{-1,-1};
        // 确保目标值要小于int的最大范围
        if (target > Integer.MAX_VALUE)
            return new int[]{-1,-1};
        for (int i = 0; i < nums.length; i++ ) {
            int j = i + 1;
            while(j < nums.length) {
                if ((nums[i] + nums[j]) == target) {
                    result[0] = i;
                    result[1] = j;
                    break;
                }
                j++;
            }
        }
        return result;
    }

第一种解法的时间复杂度是O(n²)，空间复杂度是O(1)

第一种解法的时间复杂度主要是来自于双层循环，也就是数据遍历。于是引申出另外一种解法。使用可以快速找到元素的数据结构 Map

解法2

字典方法，空间换时间

public int[] twoSumMap(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);
        }
        return new int[2];
    }

时间复杂度为O(n)，空间复杂度为O(n)

总结

当遇到寻找特定数据的情况下，可以考虑利用 Map 的特性快速寻找，减少时间复杂度。典型的空间换时间思路。

Q.E.D.