leetcode 1. 两数之和

leetcode

1，哈希表
C++：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

        vector<int> results;
        std::map<int, int> map;
        for ( int index = 0; index < nums.size(); ++index ) {

            int number = nums[index];
            int anotherNumber = target - number;
            if ( map.find(anotherNumber) != map.end() ) {

                results.push_back(map[anotherNumber]);
                results.push_back(index);

                return results;
            }

            map[number] = index;
        }

        return results;
    }
};

2，排序 + 双指针
C++：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

        std::vector<int> temp = nums;
        std::sort(temp.begin(), temp.end());

        std::vector<int> results;
        int left = 0;
        int right = temp.size() - 1;
        while ( left < right ) {

            if ( temp[left] > target / 2 ) {

                break;
            }

            if ( temp[right] == target - temp[left] ) {

                int leftIndex = find(nums.begin(), nums.end(), temp[left]) - nums.begin();
                int rightIndex = -1;
                auto iterator = find(nums.begin() + leftIndex + 1, nums.end(), temp[right]);
                if ( iterator != nums.end() ) {

                    rightIndex = iterator - nums.begin();

                } else {

                    iterator = find(nums.begin(), nums.begin() + leftIndex - 1, temp[right]);
                    if ( iterator != nums.end() ) {

                        rightIndex = iterator - nums.begin();
                    }
                }
                results.push_back(min(leftIndex, rightIndex));
                results.push_back(max(leftIndex, rightIndex));
                ++left;
                --right;

            } else if ( temp[right] > target - temp[left] ) {

                --right;

            } else {

                // temp[right] < target - temp[left]
                ++left;
            }
        }

        return results;
    }
};