Algo: Two Sum

类似的题目可以用HashTable的思想解决。

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.

https://leetcode.com/problems/two-sum/description/

http://www.cnblogs.com/grandyang/p/4130379.html

https://blog.csdn.net/gatieme/article/details/50596965

https://segmentfault.com/a/1190000006697526

#include <vector>

#include <unordered_map>

std::vector<int> twoSum(std::vector<int>& nums, int target)

{

    int size = (int)nums.size();

    std::unordered_map<int, int> mp;

    std::vector<int> ans;

    for(int i = ; i < size; ++i)

    {

        if(mp.count(target - nums[i]))

        {

            ans.push_back(mp[target - nums[i]]);

            ans.push_back(i);

            break;

        }

        mp[nums[i]] = i;

    }

    return ans;

}

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.

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/

https://www.cnblogs.com/grandyang/p/5185815.html

#include <vector>

std::vector<int> twoSum(std::vector<int>& numbers, int target)

{

    int l = ;

    int r = (int)numbers.size() - ;

    while (l < r)

    {

        int sum = numbers[l] + numbers[r];

        if (sum == target)

        {

            return {l + , r + };

        }

        else if (sum < target)

        {

            ++l;

        }

        else

        {

            --r;

        }

    }

    return {};

}

3、

巴特西

Algo: Two Sum

最新文章

热门文章