# Leetcode 167. Two Sum II - Input Array Is Sorted
###### tags: `Leetcode(C++)`

題目 : https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/ 。

想法 :

先用index陣列當作Hash標籤去找，並事先把數字都加上1000避免負的index陣列存取。
小心可能會有兩個一樣的元素。

時間複雜度 : O(n)。

程式碼 :

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int l=numbers.size(), index[2010]={0}, first=0, second;
        vector<int> ans;
        
        for(int i=0 ; i<l ; i++){
            numbers[i]+=1000;
            index[numbers[i]]++;
        }
        target+=2000;
        
        for(  ;  ; first++){
            int tmp=target-numbers[first];
            if(index[tmp] >= 1){
                second=tmp; break;
            } 
        }
        
        for(int i=0 ; i<l ; i++){
            if(numbers[i] == second){
                if(numbers[i] == numbers[first]) second=i+1;
                else second=i;
                break;
            }
        }
        
        ans.push_back(first+1);
        ans.push_back(second+1);
        
        return ans;
    }
};