• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

LeetCode从读题到自闭:1. 两数之和

开发技术 开发技术 3小时前 1次浏览

中文题目:

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

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

你可以按任意顺序返回答案。

示例 1:

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

输入:nums = [3,2,4], target = 6
输出:[1,2]
示例 3:

输入:nums = [3,3], target = 6
输出:[0,1]

提示:

2 <= nums.length <= 10^3
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
只会存在一个有效答案

英文题目:

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

2 <= nums.length <= 10^3
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10 ^9
Only one valid answer exists.

解法1:暴力枚举

最容易想到的方法是枚举数组中的每一个数 x,寻找数组中是否存在 target – x。

当我们使用遍历整个数组的方式寻找 target – x 时,需要注意到每一个位于 x 之前的元素都已经和 x 匹配过,因此不需要再进行匹配。而每一个元素不能被使用两次,所以我们只需要在 x 后面的元素中寻找 target – x。

Demo:

 1 class Solution {
 2     public int[] twoSum(int[] nums, int target) {
 3         for (int i = 0; i < nums.length - 1; i++) {
 4             for (int j = i + 1; j < nums.length; j++) {
 5                 if (nums[j] == target - nums[i]) {
 6                     return new int[] { i, j };
 7                 }
 8             }
 9         }
10         return null;
11     }
12 }

解法2:哈希表

遍历数组 nums,i 为当前下标,每个值都判断hashtable中是否存在 target-nums[i] 的 key 值;
如果存在则找到了两个值,如果不存在则将当前的 (nums[i],i) 存入 hashtable 中,继续遍历直到找到为止。

输入:nums = [2,7,11,15], target = 22
输出:[0,1]

i=0,22-2=20不在hashtable中,[2,0]存进去;【2,0】
i=1,22-7=15不在hashtable中,[7,1]存进去;【2,0】【7,1】
i=2,22-11=11,不在hashtable中,[11,2]存进去;【2,0】【7,1】【11,2】
i=3,22-15=7,存在【7,1】

输出[1,3]

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

附:

类型 占用存储空间 表数范围
byte 1字节=8bit位 -128 ~ 127
short 2字节 -2^{15} ~2 ^{15}-1
int 4字节 -2^{31} ~ 2 ^{31}-1 (约21亿)
long 8字节 -2^{63} ~ 2 ^{63}-1

LeetCode从读题到自闭:1. 两数之和


程序员灯塔
转载请注明原文链接:LeetCode从读题到自闭:1. 两数之和
喜欢 (0)