leetcode：1. 两数之和

题目来源

• leetcode：1. 两数之和

题目描述

题目解析

数组中同一个元素不能使用两遍：比如[5, 5]，因为他们的索引不同，所以可以5 + 5

双指针

因为我们每次要从数组中找两个数。因此一个很简单的思路是：

• 使用双重循环枚举下标i和j，分别代表要找的两个数
• 然后判断nums[i] + nums[j] == target是否成立

另外为了防止重复技术，我们需要在第一层循环中让i从0开始，到n - 2结束（确保能够取到下一个数作为j；在第二层循环中让j从i + 1开始，到n - 1结束）

C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int i = 0, j = 0;
        for (i = 0; i + 1 < nums.size(); ++i) {
            int find = target - nums[i];
            for (j = i + 1; j < nums.size(); ++j) {
                if(nums[j] == find){
                    return {i, j};
                }
            }
        }
        return {};
    }

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

使用map

首先，任何优化的思路不外乎[减少重复]

从暴力中可以知道，逻辑上我们是先定下来一个数，然后从数组中往后找另一个值是否存在。但是其实我们在找第二个树的过程中重复扫描了数组多次。

举个例子，对于nums = [2,3,8,4], target = 9，我们先确定下来第一个树是2，然后从后扫描搭配最后一个数，检测是否有7。发现没有，再决策第一个数为 3 的情况，这时候我们应该利用前一次扫描的结果来帮助我们快速判断是否存在 6，而不是再重新进行一次扫描。

这是直观的优化思路，不难想到可以使用哈希表进行存储。以数值为 key，数值的下标为 value。

C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int t) {
        std::unordered_map<int, int> map;
        int n = nums.size();

        for (int i = 0; i < n; ++i) {
            map[nums[i]] = i;
        }

        for (int i = 0; i < n; ++i) {
            int a = nums[i], b = t - a;
            if(map[a] == i){
                map.erase(a); // 优化点（下一次遍历的时候可以加快速度； 而且这个key不能重复使用）
            }
            if(map.count(b)){
                return {i, map[b]};
            }
        }
        
        return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

golang

func twoSum(nums []int, target int) []int {
	hashTable := map[int]int{}

	for i, v := range nums {
		if p, ok := hashTable[target - v]; ok{
			return []int{p, i}
		}
		hashTable[v] = i;
	}


	return nil
}
1
2
3
4
5
6
7
8
9
10
11
12
13

类似题目

方案对比

不同的结构中找是否存在满足要求（和为target）的两个数

K数之和