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

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

3小时前 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

## 解法1：暴力枚举

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：哈希表

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 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