画解算法：1. 两数之和

题目链接

https://leetcode-cn.com/problems/two-sum/

题目描述

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例：

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题方案

思路1：两次for循环

• 利用两次for循环，遍历每一个元素，再将差值与其后元素一一比对，也称为“暴力法”。
• 时间复杂度为O(n^2)：n + (n-1) + .... + 1。

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    return new int[]{i, j};//返回数组最简洁
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");//非法参数异常
    }
}

思路2：两遍哈希表

• “暴力法”时间复杂度高，因为差值要一一和其后元素比较，如果差值一次就能和其他所有元素比较，那么时间复杂度为O(n)。
• 可以利用哈希表的contains()实现此功能。
• 因为需要返回索引，所以元素和索引要相关联，所以使用Map结构。
• 因为要返回索引，假设索引作为key，元素作为value，不能根据value(元素)返回其key(索引)，所以元素作为key，索引作为value。
• 两遍哈希表，第一遍将数据存放到map中，第二遍使用contains方法。

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();//引用对象使用<Integer, Integer>可指定存储类型
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);//nums[i]做key，虽nums[i]可重复，但此时value为第二个索引，可区分；nums[i]为value，不能根据value反推key（索引）。
        }
        for (int i = 0; i < nums.length; i++) {
            int key = target - nums[i];
            //map.keySet().contains(key)；利用&&特性：如果map.containsKey(key)为false，map.get(key)将空指针异常；map.get(key) != i: 索引不同，确保不是同一个元素
            if (map.containsKey(key) && map.get(key) != i) { 
                return new int[]{i, map.get(key)};
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

思路3：一遍哈希表

• 可将第一遍哈希省略，每次循环，将元素、索引存于map，当前元素可与前面的元素比较。

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int key = target - nums[i];
            if (map.containsKey(key)) {//跟前面元素比较，肯定不是同一个元素，所以不比较索引
                return new int[]{map.get(key), i};//i在后
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

画解

• 请看灵魂画师牧码的画解

测试用例

描述	1	2	3	4
nums	[2, 7, 11, 15]	[3, 2, 4]	[3, 3]	[2, 5, 5, 11]
target	9	6	6	10