0001. Two Sum.md

0001. Two Sum, easy, , freq: 10%, acceptance: 44.4%

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.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

Python

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        nums2 = [(x, i) for i, x in enumerate(nums)]
        nums2 = sorted(nums2, key=lambda x: x[0])
        i = 0
        j = len(nums2) - 1
        while(i < j):
            s = nums2[i][0] + nums2[j][0]
            if s == target:
                return sorted([nums2[i][1], nums2[j][1]])
            if s > target:
                j -= 1
            else:
                i += 1
        return [-1, -1]

C++ v1

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        using node = std::pair<int,int> ;
        vector<node> v;
        for (int i = 0; i < nums.size(); i++) {
            v.push_back(std::make_pair(nums[i], i));
        }
        sort(v.begin(), v.end());
        int i = 0, j = nums.size()-1;
        while (i < j) {
            int d = target - (v[i].first + v[j].first);
            if (d == 0) {
                vector<int> r = {v[i].second, v[j].second};
                sort(r.begin(), r.end());
                return r;
            } else if (d > 0) {
                i++;
            } else {
                j--;
            }   
        }
    }
};

C++ v2

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> m;
        for (int i = 0; i < nums.size(); i++) {
            m[nums[i]] = i;
        }
        for (int i = 0; i < nums.size(); i++) {
            int b = target - nums[i];
            if (m.count(b) > 0 && i != m[b]) {
                vector<int> r = {i, m[b]};
                sort(r.begin(), r.end());
                return r;
            }
        }
    }
};