《LeetCode刷题》——1.两数之和

@[toc]

一、题目内容

原题连接：https://leetcode.cn/problems/two-sum/

题目：

默认代码模块：

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

    }
}

二、个人答案（Java）

思路：题目要求是给一个整型的数组和目标值，判断数组中的那两个元素相加等于目标值，再把这两个数的脚标放进一个数组里面，返回这个数组，我想到的是for循环一下子就可以解决，相当于假设给定一串数，12345，遍历一下他们两两组合是否等于目标值，不能重复，就是1分别和后面的数字2345匹配，然后2又和2后面的数字345匹配......以此类推，匹配到了和等于目标值就放进一个数组里面，返回该目标值即可。没有匹配到就返回null

代码：

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

三、官方答案（Java）

ps：官方给的方法一也是for循环

方法二如下(官方答案，已备注出处)：

思路及算法

注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。

使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N)O(N)O(N) 降低到 O(1)O(1)O(1)。

这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。