寻找两个数之和算法解密

此题目来自 力扣，在下讲解下解题思路，各位看官看我思路可对。

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回[0, 1]

思路一

提示 1
A really brute force way would be to search for all possible pairs of numbers but that would be too slow. Again, it’s best to try out brute force solutions for just for completeness. It is from these brute force solutions that you can come up with optimizations.
中文意思：
一种真正的蛮力方式是搜索所有可能的数字对，但这太慢了。同样，最好尝试蛮力解决方案以确保完整性。您可以借助这些蛮力解决方案进行优化。

代码

class Solution {public int[] twoSum(int[] nums, int target) {int[] answers = new int[2];
        // 双重循环 循环极限为(n^2-n)/2 
        for(int i = 0; i < nums.length; i++){for(int j = nums.length - 1; j > i; j --){if(nums[i]+nums[j] == target){answers[0] = i;
                   answers[1] = j; 
                   return answers;
                }
            }
        }
        return answers;
    }
}

思路二

提示 2
So, if we fix one of the numbers, say
x, we have to scan the entire array to find the next number y which is value – x where value is the input parameter. Can we change our array somehow so that this search becomes faster?
中文意思：
如果我们固定其中一个数字 x，我们必须扫描整个数组以找到下一个数字 y，即值 -x，其中 value 是输入参数。我们可以以某种方式更改数组以使搜索更快吗？

代码

class Solution {public int[] twoSum(int[] nums, int target) {int[] answers = new int[2];
        List<Integer> list = new ArrayList<>(nums.length);
        for(int i = 0; i < nums.length; i++){if(list.contains(nums[i])){answers[0] = list.indexOf(nums[i]);
                answers[1] = i;
                return answers;
            }
            list.add(target - nums[i]);
        }
        return answers;
    }
}

我类个叉叉叉，为什么执行时间增加了，内存也增加了，越写越垃圾，??。这地方先不解释为什么了，下面给统一解释。

思路三

提示 3
The second train of thought is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?
中文意思：
第二个思路是，在不更改数组的情况下，我们可以以某种方式使用额外的空间吗？像 hash map 一样可以加快搜索速度？

这提示，我想不用说什么了吧直接上吧。

代码

class Solution {public int[] twoSum(int[] nums, int target) {int[] answers = new int[2];
        HashMap<Integer,Integer> hash = new HashMap<>(nums.length);
        for(int i = 0; i < nums.length; i++){if(hash.containsKey(nums[i])){answers[0] = hash.get(nums[i]);
                answers[1] = i;
                return answers;
            }
            // 将数据存入 key 为补数，value 为下标
            hash.put(target-nums[i],i);
        }
        return answers;
    }
}

总结

• 思路一: 不用我说了吧，就是双层循环，没有可解释的，大部分人的做法。
• 思路二: 想法很简单，就是我们把目标值和你循环的值做差，然后存在相差的 list，然后下一个循环的值如果在差值 list 里就寻找到了这个两个值。看似是时间复杂度是 O(n), 如果你看过 list 的源码你会发现，你想想的只是想象，我们来看一看思路二程序的源码部分

//list.contains(nums[i])
//list.indexOf(nums[i])
public boolean contains(Object o) {return indexOf(o) >= 0;
}

public int indexOf(Object o) {if (o == null) {for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

是不是心态爆炸，那我们来计算它的时间复杂度，它的时间复杂度和下面的相同

 for (int i = 0; i < n; i++) {for (int j = 0; j <= i; j++) {for (int z = 0; z <= i; z++) {}}
}

那时间复杂度呢？
$1^2+2^2+3^2+…+n^2=n(n+1)(2n+1)/6$
哈哈，是不是发现那个耗时是正常的。有些时候看似简单代码往往最致命。那就有人问 hash.containsKey(nums[i]) 那它为什么这么快，这就需要看看 HashMap 源码了。

• 思路三: HashMap 根据 key 找 value 时间复杂度是 O(1) 所以我们就用 HashMap，下面我们来看看hash.containsKey(nums[i]) 的源码

public boolean containsKey(Object key) {return getNode(hash(key), key) != null;
}

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

也许看不懂 getNode(int hash, Object key) 这个方法，但是我们可以看出 containsKey(Object key) 和get(Object key)雷同，我们都知道 HashMap 的get方法时间复杂度是O(1) 所以思路三的时间复杂度整体是O(1)。

到此这个题目的一步步解题思路就呈现在我们眼前。各位看官你们可有最优解。