001两数之和

题意

给出一个数组和一个目标值，让你在数组中找出和为目标值的两个数，并且这两个数在数组中的下标（索引）不同。

示例

输入：nums=[2,7,11,15],target=9

输出：[0,1]

解释：因为nums[0]+nums[1]==9，返回[0,1]

分析

所谓的“暴力”，在算法领域表示“穷举、极低效率的实现”。主要源于这个英文单词（Brute-Force，暴力攻击）。

两层遍历，第一层确定第一个数，第二层确定第二个数，用一个加法运算就可以完成题目的要求。

classSolution{
//定义一个方法twoSum，接收一个整数数组nums和一个目标值target
publicint[]twoSum(int[]nums,inttarget){
//外层循环遍历数组中的每个元素
for(inti=0;i<nums.length;i++){
//内层循环从当前元素的下一个开始遍历
for(intj=i+1;j<nums.length;j++){
//检查当前选中的两个数之和是否等于目标值
if(nums[i]+nums[j]==target)
//如果等于目标值，返回这两个数的索引
returnnewint[]{i,j};
}
}

//如果遍历完数组都没有找到符合条件的两个数，则抛出异常
thrownewIllegalArgumentException("没有找到");
}
}

笔试如果遇到不太会的题，就暴力。不过两次遍历的时间复杂度是 。

时间复杂度，在算法领域是一个非常重要的概念，一个衡量算法执行时间随输入数据规模增长而增长的度量。在这个特定的 “两数之和” 问题的解法中，时间复杂度是由两层嵌套循环决定。

时间复杂度实在是太不理想，效率太低，在所有 Java 提交中只能击败不到 28% 的用户。

虽然击败了 33% 的 Java 选手，但是这样的算法时间复杂度和之前相比根本没有变化。

我们反推一下。

已知 i 和 target，那么target - i就是与 i 相配对的另一个数，我们只需要判断target - i是否在 i 之前出现过，如果出现过，那么这两个数就是我们要找的数。

那么问题来了，如何判断target - i是否在 i 之前出现过呢？

我们可以用一个 HashMap 来记录数组中的每一个元素，元素的索引作为哈希表的 key，元素本身作为 value，当发现target - i在哈希表中存在时，就可以直接返回这两个数的索引了。来看题解。

class Solution {
    //定义一个方法twoSum，接收一个整数数组nums和一个目标值target
    public int[] twoSum(int[] nums, int target) {
        //定义一个HashMap用于存储数组元素以及他的索引

        HashMap<Integer,Integer> map = new HashMap<>();
        //遍历数组中的每一个元素
        for(int i = 0 ;i<nums.length;i++){
            //计算与当前元素配对的元素
            int complement = target - nums[i];
            //检查HashMap中是否已经存在配对元素
           if(map.containsKey(complement)){
               //存在，就将两元素的下标进行返回
               return new int[]{i , map.get(complement)};
           }
           //将当前元素及其索引添加到哈希表中
           map.put(nums[i] ,i);

        }
       
throw new IllegalArgumentException("没找到");

    }
}

当输入是 nums = [2,7,11,15] 和 target = 9 时，我们来模拟上述解决 “两数之和” 的整个过程：

1. 初始化哈希表：开始时，哈希表为空。
2. 遍历数组：
3. 第一个元素（i = 0）：nums[0] = 2
4. 计算 complement = target - nums[i] = 9 - 2 = 7。
5. 检查哈希表中是否存在 7。目前哈希表为空，所以不存在。
6. 将 (2, 0) 加入哈希表（值为 2，索引为 0）。
7. 第二个元素（i = 1）：nums[1] = 7
8. 计算 complement = 9 - 7 = 2。
9. 检查哈希表中是否存在 2。是的，它存在，并且索引为 0。
10. 找到匹配的一对元素：nums[0] = 2 和 nums[1] = 7，它们的和为 9。
11. 返回这两个元素的索引 [1, 0]。

因此，对于输入 nums = [2,7,11,15] 和 target = 9，该题解会返回 [1, 0] 作为结果，表示 nums 数组中索引为 1 和 0 的元素相加得到目标值 9。

时间复杂度：

空间复杂度：

哦吼，这次结果就不一样了，打败了 71% 的选手，效果显著。

总结

对于本题，我们用到了 Java 中的一个普通 for 循环，和一个 HashMap，这两个都是 Java 中必须掌握的知识，如果你对这两个都不熟悉，那么你的 Java 基础还是不够扎实。

建议通过下面三个链接来学习：

1. Java for 循环
2. 数组
3. HashMap

力扣链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了