# Two Sum
###### tags: `winter lc`

# Problem

# Solution

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        return hash_sol(nums, target);
    }
    
    
    vector<int> hash_sol(vector<int> &nums, int target) {
        std::map<int, int> cont;
        std::vector<int> ans;
        
        // iterator performance is better than indice ????
        for (int i = 0; i < nums.size(); i++) { // compiler would optimize this
            int curVal = nums[i];
            if (cont.find(target - nums[i]) != cont.end()) {
                ans.push_back(i);
                ans.push_back(cont[target - curVal]);
                break;
            }
            
            cont[curVal] = i;
        }
        
        return ans;
    }
    
    // could not find correct index
    vector<int> sort_sol(vector<int> &nums, int target) {
        std::sort(nums.begin(), nums.end());
        int low = 0, high = nums.size() - 1;
        std::vector<int> ans;
        
        while (low < high) {
            int sum = nums[low] + nums[high];
            if (sum > target) {
                high -= 1;
            }
            
            else if (sum < target) {
                low += 1;
            }
            
            else {
               ans.push_back(low);
               ans.push_back(high); 
            }
        }
        
        return ans;
    }
    
};

// have exactly one solution
// the same element could not use twice
// question
// element in array unique ?? nope
// the range of element (all positive, integer, floating point (single precision, double precision problem, overflow (how to handle overflow)))
// e.g. 2 ^ 31 + 2 ^31

// solution 1 : two for loop
// O(n^2)

// solution 2: hash (map)

// solution 3: binary search (sorted array)


// testcases
// ordered list [1,2,3,4,5] target = 8
// not ordered list [3,4,4,3] target = 6