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] Output: 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?
Companies:
Amazon, Adobe, Google, Apple, Microsoft, Facebook, Bloomberg, Uber, SAP, Cisco, Paypal, tcs, Yahoo, Oracle, Expedia, Walmart Labs, VMware, Intel, Goldman Sachs, Morgan Stanley
Related Topics:
Array, Hash Table
Similar Questions:
- 3Sum (Medium)
- 4Sum (Medium)
- Two Sum II - Input array is sorted (Easy)
- Two Sum III - Data structure design (Easy)
- Subarray Sum Equals K (Medium)
- Two Sum IV - Input is a BST (Easy)
- Two Sum Less Than K (Easy)
- Max Number of K-Sum Pairs (Medium)
- Count Good Meals (Medium)
// OJ: https://leetcode.com/problems/two-sum/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
vector<int> twoSum(vector<int>& A, int target) {
vector<vector<int>> v;
int N = A.size(), L = 0, R = N - 1;
for (int i = 0; i < N; ++i) v.push_back({ A[i], i });
sort(begin(v), end(v));
while (L < R) {
int sum = v[L][0] + v[R][0];
if (sum == target) return { v[L][1], v[R][1] };
if (sum < target) ++L;
else --R;
}
return {};
}
};
// OJ: https://leetcode.com/problems/two-sum/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
vector<int> twoSum(vector<int>& A, int target) {
unordered_map<int, int> m;
for (int i = 0; i < A.size(); ++i) {
int t = target - A[i];
if (m.count(t)) return { m[t], i };
m[A[i]] = i;
}
return {};
}
};