[Arrays and Strings] 1.Two sum - LeetCode

https://leetcode.com/problems/two-sum/description/

Two Sum - LeetCode

 

• 코드 템플릿 :  1. Two pointers: one input, opposite ends 
• Time complexity: O(n)
• 숙지할것:

1. Two pointers 는 SORTED 된 ARRAY에 바로 쓸수있으며 위 문제는 SORTED 가 되지않음

2. std::pair 포맷 숙지**

3. std::sort 포맷 숙지**

---

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int left=0;
        int right = int(nums.size())-1;
        vector<pair<int,int>> pair_v; // 포맷 숙지
        
        for(int i= 0 ; i<nums.size(); i++){
            pair_v.push_back({nums[i],i}); // push back 포맷숙지
        }

        sort(pair_v.begin(),pair_v.end()); //std::sort 포맷 

        while( left< right ){

            int value = pair_v[left].first+pair_v[right].first;
            if( value == target ){
                return {pair_v[left].second,pair_v[right].second};
            }

            if(value<target){
                left++;
            }
            else{
                right--;
            }

        }

    return {-1,-1};
    }
};

// sort 가 안되있는 상태로 컨디션을 ??