两数之和

发表于 分类于 ， ， 阅读次数：

题目描述

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

示例：

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

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

我的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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};
                }
            }
        }
        return null;
    }
}

本题我的方法是直接暴力，直接两个数按顺序组合起来看是否等于target，等于就返回结果。

运行结果

执行用时：55 ms, 在所有 Java 提交中击败了25.59%的用户

内存消耗：41.8 MB, 在所有 Java 提交中击败了26.16%的用户

通过测试用例：57 / 57

大神题解

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i< nums.length; i++) {
            if(map.containsKey(target - nums[i])) {
                return new int[] {map.get(target-nums[i]),i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

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

我的理解为创立一个空哈希表，往里面不断放数，放数的同时存入数的下标，一旦检测到target减去即将要放入的数的结果在哈希表时，此时这两个数就是目标结果，调用get获得目标下标，输出当前待存入数下标即为结果。这样大大减少了运算时间。