算法--两数之和

问题描述：

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

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

Java算法一：

暴力遍历--我的杰作

暴力遍历算法-1

后来我知道。可以 return new int[] {i,j}；嗯，的确又优化了我的代码，好开心(｡◕ˇ∀ˇ◕)。

但是！但是啊！耗时长啊，关于时间复杂度可以看这里，反正就是耗时长，优秀的我当然不会妥协的呀。↓↓↓↓↓

---

Java算法二：

两遍哈希表？？？？--来自LeetCode，学习学习。

哈希表什么鬼？黑人问号。

看这里看这里，学习到了。-->>哈希表

引用自LeetCode

为了对运行时间复杂度进行优化，我们需要一种更有效的方法来检查数组中是否存在目标元素。如果存在，我们需要找出它的索引。保持数组中的每个元素与其索引相互对应的最好方法是什么？哈希表。

通过以空间换取速度的方式，我们可以将查找时间从O(n)O(n)O(n)降低到O(1)O(1)O(1)。哈希表正是为此目的而构建的，它支持以近似恒定的时间进行快速查找。我用“近似”来描述，是因为一旦出现冲突，查找用时可能会退化到O(n)O(n)O(n)。但只要你仔细地挑选哈希函数，在哈希表中进行查找的用时应当被摊销为O(1)O(1)O(1)。

一个简单的实现使用了两次迭代。在第一次迭代中，我们将每个元素的值和它的索引添加到表中。然后，在第二次迭代中，我们将检查每个元素所对应的目标元素（target−nums[i]target - nums[i]target−nums[i]）是否存在于表中。注意，该目标元素不能是nums[i]nums[i]nums[i]本身！

来自LeetCode

public int[] twoSum(int[] nums, int target)

{

    Map map = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {

        map.put(nums[i], i);//构成key,value对应的关系，数值为key,索引为value

    }

    for (int i = 0; i < nums.length; i++) {

        int complement = target - nums[i]；//求补

        if (map.containsKey(complement) && (int)map.get(complement) != i) {

//寻找除了自身以外的元素

            return new int[] { i, （int)map.get(complement) };//符合补数的下标

        }

    }

    throw new IllegalArgumentException("No two sum solution");//异常处理

}

嗯，还是这个方法好，代码少，速度快

---

算法三：

一遍哈希表：--LeetCode

事实证明，我们可以一次完成。在进行迭代并将元素插入到表中的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回。

public int[] twoSum(int[] nums, int target) {

    Map map = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {

        int complement = target - nums[i];

        if (map.containsKey(complement)) {

            return new int[] { map.get(complement), i };

        }

        map.put(nums[i], i);//放的同时找---回首望月，嘿，皮。

    }

    throw new IllegalArgumentException("No two sum solution");

}

总结就是对现有函数的熟练使用以及结题思路要找对，哎，可惜我的是加法，年轻啊骚年

加油加油--你是要称为大神的男人！

774--WELOVE