I have an algorithm written which gives result.
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.

But it is too slow,

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        res=[]
        for i in range(len(nums)):
            first_val=nums[i]
            second_val=target - nums[i]
            for j in range(len(nums)):
                if i!=j:
                    
                    if nums[j]==second_val:
                        res.append(i)
                        res.append(j)
                        return res
        return res

Could anyone assist me in rewriting this algorithm in Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

>Solution :

In O(n) time complexity it can be done as below code.

logic is as, since there is solution pair in the given input, ie sum of these value make up to target, ie val1 + val2 = target, so we need to iterate through the list and search for val2 = target – val1, if we found it then return result.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        info = {}
        for i, v in enumerate(nums):
            if target-v not in info:
                info[v] = i
            else:
                return [info[target-v], i]