30 Days of Code [Day 28]

10 Sep 2021

QUESTION : 167. Two Sum II - Input array is sorted

USING MAPS

#define vi vector<int>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define fo(i,s,n) for(int i=s;i<n;++i)
#define of(i,s,n) for(int i=s-1;i>=n;--i)
#define fv(V) for( auto &it : V )
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        fastio;
        map<int, pair<bool, int>> m1,m2;
        fo(i,0,nums.size()){
            if(nums[i] >= 0){
                m1[nums[i]].first = true;
                m1[nums[i]].second = i+1;
            }
            else{
                m2[abs(nums[i])].first = true;
                m2[abs(nums[i])].second = i+1;
            }
        }
        vi res;
        res.reserve(2);
        fo(i,0,nums.size()){
            int tf = target - nums[i];
            if(tf >= 0){
                if(m1[tf].first){
                    res.pb(i+1);
                    res.pb(m1[tf].second);
                    return res;
                }
                else{
                    if(m2[abs(tf)].first){
                        res.pb(i+1);
                        res.pb(m2[abs(tf)].second);
                        return res;
                    }
                }
            }
        }
        return res;
    }
};

USING TWO POINTERS

#define vi vector<int>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define fo(i,s,n) for(int i=s;i<n;++i)
#define of(i,s,n) for(int i=s-1;i>=n;--i)
#define fv(V) for( auto &it : V )
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        fastio;
        vi res;
        res.reserve(2);
        int l = 0;
        int r = nums.size()-1;
        while(l <= r){
            int sum = nums[l] + nums[r];
            if(target == sum){
                res.pb(l+1);
                res.pb(r+1);
                return res;
            }
            if(sum < target) l++;
            else r--;
        }
        return res;
    }
};