时间轴

2025-11-13

init

题目：

P1 两数之和

https://leetcode.cn/problems/two-sum/submissions/677935101/?envType=study-plan-v2&envId=top-interview-150

排序+双指针

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
39
#include <vector>
#include <algorithm>
#include <unordered_map>

using std::vector;
using std::unordered_map;

class Solution {
    public:
	vector<int> twoSum(vector<int> &nums, int target)
	{
		unordered_map<int, vector<int> > num2index;
		int i, n = nums.size();
		for (int i = 0; i < n; i++) {
			if (!num2index.count(nums[i])) {
				num2index[nums[i]] = vector<int>();
			}
			num2index[nums[i]].push_back(i);
		}
		std::sort(nums.begin(), nums.end());
		int left = 0, right = n - 1;
		while (left < right) {
			if (nums[left] + nums[right] < target) {
				left++;
			} else if (nums[left] + nums[right] > target) {
				right--;
			} else {
				break;
			}
		}
		vector<int> res;
		if (nums[left] == nums[right]) {
			res = { num2index[nums[left]][0], num2index[nums[right]][1] };
		} else {
			res = { num2index[nums[left]].front(), num2index[nums[right]].front() };
		}
		return res;
	}
};

哈希表一次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <vector>
#include <algorithm>
#include <unordered_map>

using std::vector;
using std::unordered_map;

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

};