1 - Two Sum & 167 - Two Sum II - Input Array Is Sorted

1 - Two Sum

#easy

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

首先我在強調一下 什麼時候使用哈希法，當我們需要查詢一個元素是否出現過，或者一個元素是否在集合裡的時候，就要第一時間想到哈希法。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map <int,int> map;
        for ( int i = 0; i < nums.size(); i++ ) {
			      // 遍歷當前元素，並在map中尋找是否有匹配的key
            auto iter = map.find( target - nums[i] );
            if ( iter != map.end() ) {
                return {i, iter->second};
            }
            
		        // 如果沒找到匹配對，就把訪問過的元素和下標加入到map中
            map.insert( pair<int,int>(nums[i], i ) );
        }
        return {};
    }
};

167 - Two Sum II - Input Array Is Sorted

#medium

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Example 1:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:
Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        // two pointer
        int left = 0;
        int right = numbers.size() - 1;
        vector<int> result;
        while ( left < right ) {
            int sum =  numbers[left] + numbers[right];
            if ( sum == target ) {
                result.push_back( left + 1 );
                result.push_back( right + 1 );
                break;
            }
            else if ( sum > target ) right--;
            else left++;
        }

        return result;
    }
};