两数之和

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

  • 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
  • 你可以按任意顺序返回答案。

1.暴力法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int i, j;
        for (i = 0; i < nums.size(); ++i) {
            for (j = i + 1; j < nums.size(); ++j) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return {i, j};
    }
};

2.二分查找

思想：sort排序 + 二分查找

  1. 使用for循环遍历数组中的每一个数字

  2. 在for循环内部，使用target值减去当前遍历的数字值获取配对值ret，使用二分查找该数字ret

  3. 如果找到该数字则直接输出其下标(初始若有序的情况下)

  4. 实际是无序的！难点在于如何联系被sort打乱下标后的vec与未打乱的nums，并从其中找出目标数字的下标？

    1
    2
    3
    4
    for (int j = 0; j < n; j++) {
        if (nums[j] == vec[i] || nums[j] == ret) result.push_back(j);
        if(result.size() == 2) return result;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//自己写二分差查找
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {		
		vector<int> vec;
        int n = nums.size();
        //1.遍历nums将数据拷贝到vec中
		for (auto &temp: nums) {
            vec.push_back(temp);
        }
        //2.对vec进行排序
		sort(vec.begin(), vec.end());
        //3.开始二分查找
		for (int i = 0; i < n; i++) {
            //(1)获取配对值
			int ret = target - vec[i];
            //(2)查找配对值ret在vec中的下标lower_bound(array.begin(),array.end(),targetNumber)
            //该方法返回一个指针，要获取下标只需将p与array.begin()做一次减法即可
			int idx = lower_bound(vec.begin(), vec.end(), ret) - vec.begin();
			//(3)在vec中找到了配对值ret对应的下标idx
            if(0 <= idx && idx < n && vec[idx] == ret) {
				vector<int> result;
                //(4)获取配对值ret在nums中的下标(解决sort顺序打乱的问题)
				for (int j = 0; j < n; j++) {
					if (nums[j] == vec[i] || nums[j] == ret) result.push_back(j);
					if(result.size() == 2) return result;
				}
			}
		}
        return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//利用stl提供的lower_bound二分查找
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> vec;
        //1.遍历nums将数据拷贝到vec中
		for (auto &temp: nums) {
            vec.push_back(temp);
        }
        //2.对vec进行排序
        sort(vec.begin(), vec.end());
        //3.开始二分查找
        for (int i = 0; i < vec.size(); ++i) {
            //(1)获取配对值
            int ret = target - vec[i];
            //(2)二分查找配对值ret
            int l = i + 1;
            int r = vec.size() - 1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (ret == vec[mid]) {
                    //从有序的vec中找到对应在无序的nums中的下标
                    vector<int> result;
                    for (int j = 0; j < vec.size(); ++j) {
                        if (nums[j] == vec[i] || nums[j] == ret) result.push_back(j);
					    if(result.size() == 2) return result;
                    }
                }
                if (ret < vec[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
        }
        return {};
    }
};

3.双指针

思想：sort排序 + 双指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> vec;
        //1.遍历nums将数据拷贝到vec中
		for (auto &temp: nums) {
            vec.push_back(temp);
        }
        //2.对vec进行排序
        sort(vec.begin(), vec.end());
        //3.使用双指针法在有序vec容器中进行查找
        int l = 0;
        int r = vec.size() - 1;
        while (l < r) {
            int sum = vec[l] + vec[r];
            if (sum == target) {
                vector<int> result;
                for (int i = 0; i < nums.size(); i++) {
					if (nums[i] == vec[r] || nums[i] == vec[l]) result.push_back(i);
					if(result.size() == 2) return result;
				}
            }
            if (sum > target) {
                --r;
            } else {
                ++l;
            }
        }
        return {};
    }
};

4.哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> hashmap;
        vector<int> result(2,-1);
        for (int i = 0; i < nums.size(); i++) {
            hashmap.insert(map<int, int>::value_type(nums[i], i));
        }
        for (int i = 0; i < nums.size(); i++) {
            //判定是否找到目标元素 且目标元素不能是本身
            if(hashmap.count(target - nums[i]) > 0 && (hashmap[target - nums[i]] != i)) {
                result[0] = i;
                result[1] = hashmap[target - nums[i]];
                break;
            }
        }
        return result;
    };
};

哈希表优化（减少for循环次数）：

  1. 在进行迭代将元素插入到表中的同时，就可以马上进行检查,表中是否已经存在当前元素所对应的目标元素
  2. 如果存在，那我们已经找到了对应解，并立刻将其返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//哈希表优化
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> hashmap;
        vector<int> result(2,-1);
        for(int i = 0; i < nums.size(); ++i) {
            if (hashmap.count(target - nums[i]) > 0) {
                //1.检查表中是否已经存在当前元素所对应的目标元素
                result[0] = hashmap[target - nums[i]];
                result[1] = i;
                break;
            } else {
                //2.若不存在则再将下标与data反过来放入map中,以便用来获取下标
                hashmap[nums[i]] = i;
            }
        }
        return result;
    };
};