# 1.two-sum

## Statement

• Difficulty: Easy
• Tag: `数组` `哈希表`

``````输入：nums = [2,7,11,15], target = 9

``````

``````输入：nums = [3,2,4], target = 6

``````

``````输入：nums = [3,3], target = 6

``````

• `2 <= nums.length <= 104`
• `-109 <= nums[i] <= 109`
• `-109 <= target <= 109`
• 只会存在一个有效答案

• Difficulty: Easy
• Tag: `Array` `Hash Table`

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]
Explanation: 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 <= 104`
• `-109 <= nums[i] <= 109`
• `-109 <= target <= 109`
• Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than `O(n2) `time complexity?

## Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define lowbit(x) ((x) & (-(x)))
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
vector<int> twoSum(vector<int> &nums, int target) {
vector<PII> v;
int n = nums.size();

for (int i = 0; i < n; i++) {
v.emplace_back(MP(nums[i], i));
}

sort(all(v));

int i = 0, j = n - 1;

for (; i < n; i++) {
while (j > 0 && v[i].fi + v[j].fi > target) {
--j;
}

if (v[i].fi + v[j].fi == target) {
break;
}
}

return {v[i].se, v[j].se};
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````