C++ Algorithms to Find Pair of Sum Given a Collection of Numbers

  • 时间:2020-09-27 14:36:16
  • 分类:网络文摘
  • 阅读:86 次

This is quite similar to the Two Sum puzzle.

Given a collection of numbers, write a function that finds a pair that will sum to a given value. For example, the sum we are looking for is 10 and the collection may be [2, 0, 11, 9, 7] or [5, 2, 1, 5]. The function need only return a boolean on whether any pair within the collection satisfies the condition, so False and True for the first and second collection in the example, respectively. You can assume all numbers are integers.

Assume the collection is UNORDERED. Try to find a solution that minimizes the TIME complexity.

What is the time complexity of your solution? Use big-O notation.
What is the memory complexity of your solution? Use big-O notation.

The following is the C++ psue-do code. The idea is to use a hash set that reduces the lookup time to O(1). We need to take care of the duplicate numbers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// O(n) space and O(n) time
bool findPair(const vector<int> &nums, int sum) {
    unordered_set<int> hash;
    // enter all these numbers in a hash table
    for (const auto &n: nums) {
        if (!hash.count(n)) {
            hash.include(n);
        } else {
            if (sum - n == n) { // make sure duplicate number sums.
                return true;
            }
        }
    }
    for (const auto &n: nums) {
        // if the other is existent
        if (hash.count(sum - n)) {
            return true;
        }
    }
    return false;
}
// O(n) space and O(n) time
bool findPair(const vector<int> &nums, int sum) {
    unordered_set<int> hash;
    // enter all these numbers in a hash table
    for (const auto &n: nums) {
        if (!hash.count(n)) {
            hash.include(n);
        } else {
            if (sum - n == n) { // make sure duplicate number sums.
                return true;
            }
        }
    }
    for (const auto &n: nums) {
        // if the other is existent
        if (hash.count(sum - n)) {
            return true;
        }
    }
    return false;
}

Given a collection of numbers, write a function that finds a pair that will sum to a given value. For example, the sum we are looking for is 10 and the collection may be [2, 0, 11, 9, 7] or [5, 2, 1, 5]. The function need only return a boolean on whether any pair within the collection satisfies the condition, so False and True for the first and second collection in the example, respectively. You can assume all numbers are integers.

Assume the collection is ORDERED. Try to find a solution that minimizes the TIME AND MEMORY complexity.

What is the time complexity of your solution? Use big-O notation.
What is the memory complexity of your solution? Use big-O notation.

If the collection is sorted, we can use two pointers starting at both ends, moving towards each other depending on the sum comparison.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// O(N) - time, and O(1) space
bool findPair(const vector<int> nums, int sum) {
    auto i = 0;
    auto j = nums.size() - 1;
    while (i < j) {
        if (nums[i] + nums[j] == sum)    {
            return true;
        }
        if (arr[i] + arr[j] < sum) {
            i ++;
        } else {
            j --;
        }
    }
    return false;
}
// O(N) - time, and O(1) space
bool findPair(const vector<int> nums, int sum) {
    auto i = 0;
    auto j = nums.size() - 1;
    while (i < j) {
        if (nums[i] + nums[j] == sum)    {
            return true;
        }
        if (arr[i] + arr[j] < sum) {
            i ++;
        } else {
            j --;
        }
    }
    return false;
}

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
WXT pre-sale is now live – is it worth it?  How to Serialize and Deserialize Binary Tree?  How to Construct Binary Tree from String (Binary Tree Deserializ  Activist’s Mother Faces Prison After One-Word Facebook Reply  Ed-Tech Start-Ups Can Allow Anyone To Become A Teacher  Russian Hacker Sold Millions Of Passwords For Less Than A $1, Sh  How To Successfully Fine-tune Your Overall Social Media Strategy  What It Really Takes To Make Money As a Blogger  How Do You Increase Website Domain Authority?  Bitcoin Expert Regrets Blogging About Rumored Bitcoin Creator 
评论列表
添加评论