LeetCode Two Sum

 Problem Description Link: https://leetcode.com/problems/two-sum/description/

Accepted Solution

/*

I have tried to avoid the solution with O(N^2). Therefore, I found the difference (x) between the target and current value and eventually checked whether x is present in the array or not. If it is, then the current position (i) and the last position ind[nums[i]] would be the answer. However, if both the current value and x are similar, in that case, you have to check the value that exists in the array multiple times. 

The complexity of the solution in O(N).

*/

class Solution {

public:

    vector<int> twoSum(vector<int>& nums, int target) {

        map<int, int>ind;

        map<int, int>cnt;

        vector<int>sol;

        for(int i=0; i<nums.size(); i++) {

            ind[nums[i]] = i; // number's indices

            cnt[nums[i]]+=1; // number's count

        }

        for(int i=0; i<nums.size(); i++) {

            int cur = nums[i];

            int x = target - cur;

            if(x == cur) {

                if(cnt[x] > 1) {

                    sol.push_back(i);

                    sol.push_back(ind[x]);

                    break;

                }

            }

            else {

                if(cnt[x] > 0) {

                    sol.push_back(i);

                    sol.push_back(ind[x]);

                    break;

                }

            }

        }

        return sol;

    }

};