twoSum

Problem

Given an array of integers, return indices of the two numbers such that they add up to a specific target.You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution 1

 vector<int> twoSum(vector<int>& nums, int target) {
        size_t mLength = nums.size();
        vector<int> mVec;
        mVec.resize(2);
        
        for (int i = 0; i < mLength - 1; i++){
            for(int j = i + 1; j < mLength; j++){
                if (nums[i] + nums[j] == target){
                    mVec[0] = i;
                    mVec[1] = j;
                    return mVec;
                }
            }//inside-for
        }//for
   }

Solution 2

std::vector<int> twoSum(std::vector<int>& nums, int target) {
        std::map<int, int> mMap;
        std::vector<int> result;
        result.reserve(2);

        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];
            
            //map.find return iterator
            auto iter =  mMap.find(complement);
        
            if (iter != mMap.end()){
                result.push_back(mMap[complement]);
                result.push_back(i);
                return result;
            }
            mMap.insert(std::pair<int, int>(nums[i], i));
        }
    }//twoSum

• Solution2是一种贪心策略，对数组进行迭代，且迭代过程通过Map辅助进行问题求解。