Top Interview 150 P1 Two Sum

---

Timeline

Timeline

2025-11-13

init

---

Problem:

P1 Two Sum

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

Sorting + Two Pointers

#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;
	}
};

Hash Table Two Pass

#include <vector>
#include <unordered_map>
using std::vector;
using std::unordered_map;

class Solution {
    public:
        vector<int> twoSum(vector<int> &nums, int target)
        {
                int i, n = nums.size();
                int curr;
                unordered_map<int, vector<int> > num2idx;
                vector<int> ret;

                for (i = 0; i < n; i++) {
                        num2idx[nums[i]].push_back(i);
                }
                for (i = 0; i < n; i++) {
                        curr = target - nums[i];
                        if (num2idx.count(curr)) {
                                if (curr == nums[i]) {
                                        if (num2idx[nums[i]].size() >= 2) {
                                                ret.push_back(num2idx[nums[i]].front());
                                                ret.push_back(num2idx[curr].back());
                                                return ret;
                                        } else {
                                                continue;
                                        }
                                } else {
                                        ret.push_back(num2idx[nums[i]].front());
                                        ret.push_back(num2idx[curr].front());
                                        return ret;
                                }
                        }
                }
                return ret;
        }
};

Hash Table One Pass

#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;
                int need;
                
                for (int i = 0; i < nums.size(); ++i) {
                        need = target - nums[i];

                        if (seen.count(need))
                                return {seen[need], i};

                        seen[nums[i]] = i;
                }
                return {};
        }

};