两数之和：二哥的LeetCode刷题笔记第一题

沉默王二

发布于 2023-09-12 17:47:16

1950

发布于 2023-09-12 17:47:16

文章被收录于专栏：沉默王二沉默王二

题意

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

示例

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]

难度

简单

分析

首先，我们能够很自然地想到暴力遍历数组的这个方法，两层遍历，第一层确定第一个数，第二层确定第二个数，从而完成题目的要求。

说句题外话，“暴力”一词在算法领域表示“穷举、极低效率的实现”，可能就是源于这个英文词（Brute-Force，蛮力攻击）。

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[i] + nums[j] == target)
                    return new int[]{i,j};
            }
        }

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

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

O(n^2)

。

时间复杂度，在算法领域是一个非常重要的概念，https://tobebetterjavaer.com/collection/time-complexity.html了解。

O(n^2)

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

我们能不能优化一下呢？

观察第二个循环，我们是从每个i的后面的数中寻找一个与之相加能够凑成目标值target的。

那我们就反过来想，能不能判断每个i前面的数是否存在与之相加能够凑成目标值target的呢？

可能你会脑袋一热写出下面这样的代码：

class Solution{
    public int[] twoSum(int[] nums,int target){
        for(int i = 0;i < nums.length;i++)
            for(int j = 0;j < i;j++)
                if(nums[i] + nums[j] == target)
                    return new int[]{i,j};
        throw new IllegalArgumentException("No two sum solution");
    }
}

但是这样的算法时间复杂度和之前相比根本没有变化。

再想一下，每一个i前面的数我们之前访问过，所以我们可以用一个HashMap来记录每一个i前面的数的出现情况以及坐标，这样子就可以快速地查到它前面的数了。

class Solution{
    public int[] twoSum(int[] nums,int target){
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i < nums.length;i++){
            int sub = target - nums[i];
            if(map.containsKey(sub))
                return new int[]{i,map.get(sub)};
            map.put(nums[i],i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

时间复杂度：

O(n)

空间复杂度：

O(Max\{nums[i]\})

这次结果就不一样了，打败了 70.02% 的选手。