leetcode笔记--SUM问题

引用自 http://blog.****.net/wangxiaojun911/article/details/18922337，此处仅作为自己参考

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.

方法1：//该算法找出排好序的vector中相加等于target的两个数值 //最小和最大相加，然后和target比较。如果和比较小，则左侧移动；如果和比较大，右侧移动

    class Solution {
    public:
        /*Below is the 2 sum algorithm that is O(NlogN) + O(N)*/
        /*Alternative: hash从左往右扫描一遍，然后将数及坐标，存到map中。然后再扫描一遍即可。时间复杂度O(n)*/
        vector<int> twoSum(vector<int> &numbers, int target) {
            vector<int> numbersCopy;
            for(int i = ; i < numbers.size(); i++) numbersCopy.push_back(numbers[i]);  

            sort(numbersCopy.begin(), numbersCopy.end()); //O(NlogN)
            vector<int> returnNumbers = twoSumAlgorithm(numbersCopy, target);//O(N)
            //遍历查找返回的两个值的下标，时间复杂度为O(n);
            vector<int> returnIndexes;
            for(int j = ; j < returnNumbers.size(); j++)
                for(int i = ; i < numbers.size(); i++)//O(N)
                    if(numbers[i] == returnNumbers[j]) returnIndexes.push_back(i + );  

            if(returnIndexes[] > returnIndexes[]){
                returnIndexes[] = returnIndexes[]^returnIndexes[];
                returnIndexes[] = returnIndexes[]^returnIndexes[];
                returnIndexes[] = returnIndexes[]^returnIndexes[];
            }  

            return returnIndexes;
        }  

        /*Core algorithm is linear*/
        //该算法找出排好序的vector中相加等于target的两个数值
        //最小和最大相加，然后和target比较。如果和比较小，则左侧移动；如果和比较大，右侧移动
        vector<int> twoSumAlgorithm(vector<int> &numbers, int target) {
            int len = numbers.size();
            vector<int> r;
            int i = ; int j = len - ;
            while(i < j){
                int x = numbers[i] + numbers[j];
                if(x == target){
                    r.push_back(numbers[i]);
                    r.push_back(numbers[j]);
                    i++; j--;
                }else if(x > target) j--;
                else i++;
            }
            return r;
        }
    };  

方法2：//unordered_map

2.Three SUM