Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Leet > Two Sum
  1. Brute force solution twoSumExpensive. Select every element and find the remainder after that iterate over the array to check if remainder exists in the remaining array or note.

  2. Better solution using the Hash table. Iterate over all elements and check if the remainder is present in hash table or not if not set the number and it's index using map[nums[i]] = i

// https://leetcode.com/problems/two-sum/
// https://www.youtube.com/watch?v=dRUpbt8vHpo&list=PLgUwDviBIf0rVwua0kKYlsS_ik_1lyVK_&index=2
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

class Solution {
public:
    vector<int> twoSumExpensive(vector<int>& nums, int target) {
        vector<int> mp;
        for (int i = 0; i < nums.size(); i++) {
            int rem = target - nums[i];
            for (int j = i+1; j < nums.size(); j++) {
                if (nums[j] == rem)  {
                    mp.push_back(i);
                    mp.push_back(j);
                    return mp;
                }
            }
        }
        return mp;
    }
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        unordered_map<int, int> mapp;
        for (int i = 0; i < nums.size(); i++) {
            if (mapp.find(target - nums[i]) != mapp.end()) {
                ans.push_back(mapp[target - nums[i]]);
                ans.push_back(i);
                return ans;
            } else {
                mapp[nums[i]] = i;
            }
        }
        return ans;
    }
};

int main() {
    Solution *sl = new Solution();
    // vector<int> nums = {2,7,11,15};
    // int target = 9;
    vector<int> nums = {3,2,4};
    int target = 6;
    vector<int> res;
    res = sl->twoSum(nums, target);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << " ";
    }
    
    return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment