leetcode Question 1: Two Sum

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

Analysis:
The easiest way is to use 2 loops, search every pair of elements, find the result and return the index. The idea is simple but the complexity is high ( O(n^2) ).

Let's think in another way, the above idea tracks the forward way:   A[i]+A[j]==target.
What about the opposite way?   target-A[i]==A[j].

Yep! So for each element A[i], if we know there exists A[j]== target-A[i], and the i<j, then OK!

Thus, we use hash map to store the numbers, scan the whole table and use map.find() function to find the existence of the elements. Note that the question requires (1) the index order, (2) the index is the array number +1.


Code: (O(n^2))
class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> res;
        for (int i=0;i<numbers.size()-1;i++){
            for (int j=i+1;j<numbers.size();j++){
                if (numbers[i]+numbers[j]==target){
                    res.push_back(i+1);
                    res.push_back(j+1);
                    return res;
                }
            }    
        }
        return res;
    }
};

Code(O(n)):

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> res;
        map<int,int>hmap;
        hmap.clear();
        for (int i=0;i<numbers.size();i++){
            hmap[numbers[i]]=i;
        }
        for (int i=0;i<numbers.size();i++){
            if (hmap.find((target-numbers[i]))!=hmap.end()){
                if (i<hmap[target-numbers[i]]){
                    res.push_back(i+1);
                    res.push_back(hmap[target-numbers[i]]+1);
                    return res;
                }
                if (i>hmap[target-numbers[i]]){
                    res.push_back(hmap[target-numbers[i]]+1);
                    res.push_back(i+1);
                    return res;
                }
            }
        }
    }
};



Python Version:

class Solution:
    # @return a tuple, (index1, index2)
    def twoSum(self, num, target):
        mp={}
        #construct the dict, with multiple values
        for idx, val in enumerate(num):
            mp.setdefault(val,[]).append(idx+1) 
        
        for idx,val in enumerate(num):
            if (target-val!=val and mp.has_key(target-val)): 
                return sorted((mp[target-val][0],mp[val][0]))
            if (target-val==val and len(mp[val])>1):
                return (mp[val][0],mp[val][1])




22 comments:

  1. 如果数组中有重复的话,比如a[0]=a[3]=4, target = 8,那么这个程序的结果就是错的。
    之所以通过LeetCode的debug,是因为他的数据时这样的:
    [2,1,9,4,4,56,90,3], 8
    所以歪打正着。

    ReplyDelete
    Replies
    1. 不好意思,我搞错了==
      你的是对的。

      Delete
    2. 我觉得他的代码确实无法处理下标相同(含有重复元素)的情况,应该加一个条件判定

      Delete
  2. for (int i=0;i<numbers.size();i++){
                hmap[numbers[i]]=i;
            }

    this is O( N* Log N) - so it is not O(n)

    ReplyDelete
    Replies
    1. Yes, what you said is correct. Specifically for the map<> data structure in c++, it is implemented using binary search tree and the complexity is nlogn. Here I think we can assume the hash map data structure has the O(1) complexity, of course you can find(or implement by yourself) solutions for the hash_map in c++ which has the O(1) complexity. (see my post: http://yucoding.blogspot.com/2013/08/re-viewhash-table-basics.html)


      Anyway, thanks for pointing out the specific complexity of map data structure.

      Delete
    2. This is only O(1) if you implement a hash table that discards collisions, which is perfectly valid since you only want one solution.

      Delete
  3. This comment has been removed by the author.

    ReplyDelete
  4. 有一个小bug 如果是{3,2,4} target是6 返回的是1,1 不是2,3

    ReplyDelete
    Replies
    1. I've checked the code, it seems the return value of your case is 2,3.
      res.push_back(i+1) : i+1 = 2
      res.push_back(hmap[6-2]+1) = 2+1 = 3.

      return (2,3)

      Delete
    2. sorry, man, please double check {3,2,4} target is 6.
      also the if..else is not needed.

      Delete
    3. Hey there, thanks a lot for pointing out the mistakes in the code!

      I have ignored the i==map[target-num[i]] case.

      The code is modified and now seems working well.

      Delete
  5. This comment has been removed by the author.

    ReplyDelete
  6. Hi Yu,
    After testing the easiest way, I found that it cannot be accepted by OJ, the result shows Time Limite Exceeded.

    ReplyDelete
  7. Thanks for this code..it worked on leetcode.

    ReplyDelete
  8. This comment has been removed by the author.

    ReplyDelete
  9. This comment has been removed by the author.

    ReplyDelete
  10. Time Complexity : O(N)

    int Solution::canJump(vector &A) {


    int n=A.size();
    int J=A[0];


    for(int i=1;i=i)
    J=max(J,i+A[i]);
    }

    if(J>=n-1) return 1;
    return 0;
    }

    ReplyDelete
  11. Your code is absolutely correct, but I think that the second if condition is not required. i < hmap[target-numbers[i]]) invariant is always maintained.

    ReplyDelete
  12. hey, why are you incrementing the index position everytime you push into the result vector? You don't have to do it right?

    ReplyDelete
  13. I just copy pasted the code on leetcode, its not working!! Please let me know if i have to make any changes.

    ReplyDelete
  14. Also why do we need two if conditions inside the top if condition?
    9-2 and 9-7 are going to fetch us the result right? why do we need to compare if i> or i<...

    ReplyDelete
  15. I got this when I ran your c++ O(n) solution: "error: expected unqualified-id before string constant"

    ReplyDelete