leetcode two sum problem algorithm efficiency

Question

Problem: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Here's my code:

def twoSum(nums, target):
    cnt = 0
    i = 0
    while cnt < len(nums):
        temp = 0
        if i == cnt:
            i += 1
        else:
            temp = nums[cnt] + nums[i]
            if temp == target and i < cnt:
                return [i,cnt]
            i += 1
        if i == len(nums)-1:
            i = 0
            cnt += 1

The code seems to work fine for 55/57 test cases. But it doesn't work for really big input cases. But i don't understand why this is happening because i have used only one loop and the time complexity should be O(N) which is efficient enough to run in the given time. So any idea what am i missing? And what can i do to make the algorithm more efficient?

Answer 1

if we`re not talking about space complexity:

def search(values, target):
    hashmap = {}
    
    for i in range(len(values)):
        current = values[i]
        if target - current in hashmap:
            return current, hahsmap[target - current]
        
        hashmap[current] = i

    return None

Answer 2

Your code isn't really O(n), it's actually O(n^2) in disguise.

You go through i O(n) times for each cnt (and then reset i back to 0), and go through cnt O(n) times.

For a more efficient algorithm, sites like this one (https://www.educative.io/edpresso/how-to-implement-the-two-sum-problem-in-python) have it down pretty well.

Answer 3

I am not sure of the time complexity but I think this solution will be better. p1 and p2 act as two pointers of indexes:

def twoSum(nums, target):
    nums2 = nums[:]
    nums2.sort()
    p1 = 0
    p2 = len(nums2)-1
    while nums2[p1]+nums2[p2]!=target:
        if nums2[p1]+nums2[p2]<target:
            p1 += 1
        elif nums2[p1]+nums2[p2]>target:
            p2 -= 1
    return nums.index(nums2[p1]), nums.index(nums2[p2])