Two Sum


  • 0
    J

    At the beginning, I only consider the neighbor position, obviously, it's inconsiderate.


  • -1
    K

    For solution 1 ,why does the variable j start from i+1?I have tried to begin with 1 and it still worked.
    Starting from i+1 is to reduce the complexity?


  • 0

    @KevinAI said in Two Sum:

    For solution 1 ,why does the variable j start from i+1?I have tried to begin with 1 and it still worked.

    You must have changed something else as well. I just tried that and as I had expected, it didn't get accepted (and the reason got shown).


  • -1
    W

    @KevinAI Certainly it should be accepted. Because you the steps you iterate is the super set of the steps that j starts from i+i


  • 0
    S
        retList = []
        hashT = {}
        for num in nums:
            hashT[num] = num
        for num in nums:
            if ((target - num) in hashT and nums.index(num) < nums.index(target - num)):
                retList.append(nums.index(num))
                retList.append(nums.index(target - num))
        return retList
    

    Can someone explain to me why this times out?


  • 0
    S

    Sorry this is actually the one

        retList = []
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                       if (nums[i] + nums[j] == target):
                            retList.append(i);
                            retList.append(j);
        return retList
    

    Does anyone know why it times out?


  • 1
    V

    hi smitch15, you should break out of both loops once you find the answer. If you don't and the list is big then it may take long time for it to execute. for thousand entries, 1000^2 = 1000000 iterations.


  • 0
    R

    Solution in Swift Using Dictionaries ->

    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {

    var dict = [Int: Int]()
    
    for (index, value) in nums.enumerated() {
        dict[value] = index
    }
    
    for (index, value) in nums.enumerated() {
        let otherIndex: Int! = dict[(target - value)]
        if otherIndex != nil && otherIndex != index {
            return [index, otherIndex]
        }
    }
    
    return []
    

    }


  • -1
    S

    I am sure why Approach 2 is accepted - it will not work when there are duplicate elements like test case.
    [2,5,5,11]
    10
    Map will loose one of the five's index.


  • 0

    @sharan.avinav Still wondering why you people keep making these false claims. Are you too lazy to test? Do you enjoy embarrassing yourselves? I don't get it.


  • 0
    S

    @VinzDude Thanks! I didn't realize that i understood the question wrong from the start -__-


  • 0
    C

    I was failed many times."Rumtime Error!!!" memery collapse´╝îI forgot to initialize a temporary variable.
    for(int i;i<num.size(),i++){...} Really embarrassing.


  • 0
    D

    If the use case is [3, 4, 4, 5], the result is 9. The value returned by Approach 1 and Approach 3 is different because the hash table stores the array value instead of the subscript.


  • -1
    C

    C compiler:
    int* twoSum(int* nums, int numsSize, int target) {
    int j, i;
    int *test = NULL;
    test = (int )malloc(2sizeof(int));
    for (i=0; i<numsSize ;i++)
    {
    for (j=i+1; j<numsSize ;j++)
    {
    if(nums[i]+nums[j] == target)
    {
    *(test) = i;
    *(test+1) = j;
    }
    }
    }
    return test;
    }


  • 0
    K

    @dejunyu Hi! You missed part of the task "You may assume that each input would have exactly one solution". There is no way to have 4....4.....5 in your array.


  • 0
    C

    @Kozyyy Hi, I don't understand what you mean. Can you describe clearly?


  • 0
    W

    @ManuelP Brah, I see that you've been around 2 years so you might know more than me about this community when you refer to "you people" embarrassing themselves and being lazy, but there is no reason to pull a newbie down for trying to understand a solution.

    @sharan-avinav Stepping through Approach #2 with your test case ([2,5,5,11], target = 10),

    When it iterates the first time through the array, it puts the (Key, Value) pair (5, 1) first then updates the (Key, Value) pair to (5, 2) "losing the index" as you said.

    But when you look at the second iteration (2nd for loop), it is using the array's index to look up values in the hash table so there is no "losing the index" as you said. When the array first looks at index = 1 at the first 5, the IF statement PASSES because the map.containsKey(5) is TRUE and map.get(complement) != 1 returns true because map.get(complement = 5) returns 2.

    So then Approach #2 should return new int[] = {1,2} for your test case.

    Next time, try to step through the solutions with your test case. It can take a lot of time if you are new to this but you will get faster with practice. If you are new, then I suggest going slowly with pen and paper and/or using a code visualizer which you can find for free online.


  • 1

    One Pass python solution

      def twoSum(self, nums, target):
        num_dict = {}
        for i in range(len(nums)):
           complement = target - nums[i]
           if complement in num_dict:
             return [num_dict[complement], i]
           else:
             num_dict[nums[i]] = i
    

  • 0
    D

    @Kozyyy I don't understand this meaning.Thanks.


  • -1
    C

    One pass JavaScript solution

    let twoSum = (array, target) => {
    for(let n=0;n<array.length;n++){
    let complete = target - array[n];
    let index = array.indexOf(complete,n+1);
    if(index !==n && index !== -1 ){
    return [n,index]
    }
    }
    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.