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?

CodePudding user response：

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

CodePudding user response：

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.