Two Sum Problem


Description

LeetCode Problem 1. Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Example:

1
2
3
Input: nums = [2,7,11,15], target = 9.
Output: [0,1].
Explanation: As nums[0] + nums[1] = 2 + 7 = 9, we return [0, 1].


Solution

Brute Force Approach

A simple solution is to use the brute force approach.

We loop through each element x in the array. For each element, we loop through the rest elements again to see whether target-x exists.

The time complexity of this approach is O(n2), and the space complexity is O(1).

Hash Table Approach

We can use hash table to reduce the time complexity.

For each element x in the array, we use a hash table to store the <x, index> pair, indicating we have encountered a value x and its index in the array.

When we loop through the array, we would like to know whether the sum a newly encountered element x’ and a previously encoutered element x is target (x + x’ = target). We can search (target-x’) in the hash table to see if we have encountered such an x before.

If such an x exists, we are done; otherwise, we can keep on looping through the array.

With the help of the hash table, we only need to loop through the array once. Thus, the time complexity can be reduced to O(n), while the space complexity will be increased to O(n).


Sample C++ Code

This is a C++ implementation of the hash table approach.

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
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
    map<int, int> ht;
    vector<int> ans;
    for (int i = 0; i < nums.size(); i ++) {
        int xprime = nums[i];
        int x = target - xprime;
        if (ht.find(x) != ht.end()) {
            ans.push_back(ht[x]);
            ans.push_back(i);
            break;
        }
        ht[xprime] = i;
    }
    return ans;
}

int main() {
    vector<int> nums={2, 7, 11, 15};
    int target = 9;
    vector<int> ans; 
    ans = twoSum(nums, target);
    cout << ans[0] << " " << ans[1] << endl;
}




Related Posts

Two Sum Input Array Is Sorted Problem

LeetCode 167. Given an array of integers nums sorted in...

Subarray Sum Divisible By K Problem

LeetCode 974. Given an array of integers nums and an...

Four Sum II Problem

LeetCode 454. Given four lists A, B, C, D of...

Continuous Subarray Sum Problem

LeetCode 523. Given an array of non-negative integers nums and...

Two Sum Less Than K Problem

LeetCode 1099. Given an array of integers nums and an...

Subarray Sum Equals K Problem

LeetCode 560. Given an array of integers nums and an...