Skip to content

Emmanuel Brun d'Aubignosc's site about software engineering

This is my personal blog about software and algorithms

Menu
  • About
Menu

Leetcode Two Sums C++

Posted on September 3, 2023September 8, 2023 by Emmanuel Brun d'Aubignosc

This is the first time I try Leetcode. Here is the C++ solution to my first Leetcode problem.

We have to find two different indexes, in any order, of two integers which add up to target.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

        int * arr = &nums[0];
        int size = nums.size();
        int size2 = size - 1;

    
        for (int i = 0; i < size2; i ++) {
            
            for (int ii = i + 1; ii < size; ii ++) {
                
                if ((i != ii) && (arr[i] + arr[ii] == target)) {
                    
                    nums.resize(2);
                    arr[0] = i;
                    arr[1] = ii;
                    
                    return nums;
                } 
            }
        }
        
        return (vector<int>) NULL;
    }
};

This code is very efficient for memory, but at the expense of speed, O(n2). The next code is much faster O(n), but at the expense of memory.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

        int i(0);
 
        std::multimap<int, int> mymap;
        std::multimap<int, int>::iterator it;
            
        for (int num : nums) {  
        
            mymap.insert(std::pair<int, int>(num, i));
             
            it = mymap.find(target - num);
            if (it != mymap.end() && it->second != i) {
                
                nums[0] = i;
                nums[1] = it->second;
                nums.resize(2);

                return nums;
            }

            i ++;        
        }
 
        return (vector<int>) NULL;
    }    
};

Related

Recent Posts

  • Leecode Valid Parentheses C++
  • Leetcode Two Sums Java
  • Leetcode Two Sums C++
  • Quick sort using modern C++

Recent Comments

No comments to show.

Archives

  • September 2023
  • August 2023

Categories

  • Leetcode
  • Uncategorized
© 2025 Emmanuel Brun d'Aubignosc's site about software engineering | Powered by Minimalist Blog WordPress Theme