LeetCode算法解题集：Two Sum

题目：

Given an array of integers, 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.

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

思路一：
按照第1~n每个数据遍历循环，当前指向为i的时候，则从i开始，再次向下循环对应的值与i相加是否为target，使用两次for循环。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> nResult;
        for( unsigned int i = 0; i < nums.size(); i++ )
        {
            int nFirstKey = nums[i];
            if( (nFirstKey >= target) || (nFirstKey == 0))
                continue;
             
            bool bFind = false;
            for( unsigned int k = (i + 1); k < nums.size(); k++ )
            {
                int nSecondKey = nums[k];
                if( (nFirstKey + nSecondKey) > target )
                    continue;
                 
                if( (nFirstKey + nSecondKey) == target )
                {
                    bFind = true;
                    int nIndex1;
                    int nIndex2;
                    if( nFirstKey > nSecondKey )
                    {
                        nIndex1 = k + 1;
                        nIndex2 = i + 1;
                    }
                    else
                    {
                        nIndex1 = i + 1;
                        nIndex2 = k + 1;
                    }
                    break;
                }
            }
             
            if( bFind )
                break;
        }
         
        return nResult;
    }
};

这种方式的思路比较简单，但是复杂度较高为O(n^2)。在提交时候出现 Time Limit Exceeded 错误。

思路二：
一次循环 0~n,新建一个map表，map 的key值存数字，value存索引，每次循环时，先算出需求值=target-当前值，然后去map里查找是否存在，如果存在，一切ok，如果不存在，导入，再循环下一个值，总计一个for循环。算法复杂度：O(n)!!!

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> nResult;
        map<int, int> nMap;//key: the num, value: the index
        for( unsigned int i = 0; i < nums.size(); i++ )
        {
            int nWantNum = target - nums[i];
            map<int, int>::iterator iItr;
            iItr = nMap.find(nWantNum);
            if( iItr != nMap.end() )
            {
                int nIndex1 = 0;
                int nIndex2 = 0;
                if (i > iItr->second)
                {
                    nIndex1 = iItr->second + 1;
                    nIndex2 = i + 1;
                }
                else
                {
                    nIndex1 = i + 1;
                    nIndex2 = iItr->second + 1;
                }
                 
                nResult.push_back(nIndex1);
                nResult.push_back(nIndex2);
                break;
            }
             
            iItr = nMap.find(nums[i]);
            if( iItr == nMap.end() )
            {
                nMap[nums[i]] = i;
            }
        }
         
        return nResult;
    }
};

总结：
1、算法复杂度最忌讳的是for循环嵌套。
2、换种思路，考虑map、hash这种现有的数据结果去存储结果。

本文摘录于海阔天空的博客，作者: zjg555543，发布时间: 2015-07-06