1.Two Sum

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.

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

利用hash表将value与index存起来，然后寻找target-num[i]的index

代码

vector<int> twoSum(vector<int> &numbers, int target)
{
    //Key is the number and value is its index in the vector.
    unordered_map<int, int> hash;
    vector<int> result;
    for (int i = 0; i < numbers.size(); i++) {
        int numberToFind = target - numbers[i];
        if (hash.find(numberToFind) != hash.end()) {
            result.push_back(hash[numberToFind] + 1);
            result.push_back(i + 1);            
            return result;
        }

            //number was not found. Put it in the map.
        hash[numbers[i]] = i;
    }
    return result;
}

2.Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

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

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

因为是排好序的顺序，可以利用i，j分别从前往后和从后往前遍历，nums[i]+nums[j]<target 时i++，反之j--

代码

vector<int> twoSum(vector<int>& numbers, int target) {
        int len = numbers.size();
        int i=0, j=len-1;
        while(i < j){
            if(numbers[i]+numbers[j] == target){
                vector<int> res;
                res.push_back(i+1);
                res.push_back(j+1);
                return res;
            }
            else if(numbers[i]+numbers[j] > target){
                j--;
            }
            else{
                i++;
            }
        }
        vector<int> res;
        res.push_back(i+1);
        res.push_back(j+1);
        return res;
    }

3.valid triangle number

计算数组中所有能构成三角形的组的个数。
本质上与3sum相同。我一开始的想法是先排序，然后将每个元素当做目标边，然后在后面的元素中找出可以构成三角形的二元组，因为已经排好序了，所以只要两边之差小于目标边即可。时间复杂度O（nnn）。

代码

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int len = nums.size();
        int res=0;
        sort(nums.begin(), nums.end());
        for(int i=0; i<len; i++){
            for(int j=i+1;j < len-1;j++){
                int k = len-1;
                while(nums[k]-nums[j] >= nums[i]) {
                    k--;
                }
                if(k > j) res+=k-j;
            }
        }
        return res;
    }
};

最快的算法：

时间复杂度O（n*n），先排序，将最长边作为目标，然后在小于目标边的范围内寻找二元组。二元组之差肯定小于最长边，当最左+最右元素之和大于目标边时，则最左元素右边的元素与最右元素都可以组成三角形；如果不大于则将最左元素左移一位。

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        
        sort(nums.begin(), nums.end());
        int n = nums.size(), a = 0;
        for (int i = 2; i < n; ++i) {
            int left = 0, right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    a += (right - left);
                    right--;
                } else left++;
            }
        }
        return a;
    }
};