1

1. Two Sum (Easy)

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?

Companies: Amazon, Google, Adobe, Apple, Microsoft, Yahoo, Bloomberg, Facebook, Uber, Yandex, Spotify, Oracle, Accenture, Deloitte, tcs, Tinkoff, IBM, wipro, Capgemini, Careem, Expedia, Cisco, Visa, Goldman Sachs, Morgan Stanley, Samsung, Barclays, BlackRock, eBay, Nagarro, Zillow, Accolite, Zoho, American Express, Walmart Labs, Dell, PayPal, JPMorgan, VMware, Intel, Salesforce, Infosys, MakeMyTrip, ServiceNow, Citadel, Qualcomm, ZScaler, Zoom, Zomato, Info Edge, turing, Bank of America, SAP, Grab, Intuit, Nvidia, Twitter, Deutsche Bank, Capital One, FactSet, Cruise Automation, Twitch, LinkedIn, Airbnb, Yelp, Dropbox

Related Topics:
Array, Hash Table

Similar Questions:

• 3Sum (Medium)
• 4Sum (Medium)
• Two Sum II - Input Array Is Sorted (Medium)
• 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)
• Count Number of Pairs With Absolute Difference K (Easy)
• Number of Pairs of Strings With Concatenation Equal to Target (Medium)
• Find All K-Distant Indices in an Array (Easy)
• First Letter to Appear Twice (Easy)
• Number of Excellent Pairs (Hard)
• Number of Arithmetic Triplets (Easy)
• Node With Highest Edge Score (Medium)
• Check Distances Between Same Letters (Easy)
• Find Subarrays With Equal Sum (Easy)
• Largest Positive Integer That Exists With Its Negative (Easy)
• Number of Distinct Averages (Easy)
• Count Pairs Whose Sum is Less than Target (Easy)

Solution 1.

// 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 {};
    }
};

Solution 2.

// 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 {};
    }
};