2020-02-23 Day1 Leetcode: 1. Two

A leetcode solution: Make it work->Make it right->Make it fast
you need give a right solution
you need to know how to further optimize it
you need to know how to calculate the complexity

---

During interview:
the easy case may never happen
don't need to write hurry at the beginning
think first, and communicate first, the start to write the code

---

for beginners like me:
write a solution first, then think optimize
但是一定要动手写！，而不是看

---

Screen Shot 2020-02-23 at 7.50.40 AM.png

solution1:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict={}
        for i in range(len(nums)-1):
            dict[i]=nums[i]
            for j in range(i+1,len(nums)):
                if nums[j]==target-dict[i]:
                    return [i,j]
        return False

solution2:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict={}
        for i in range(len(nums)):
            if target-nums[i] in dict.values():
                j=self.get_keys(dict,target-nums[i])
                return [i,j]
            dict[i]=nums[i]          
            
        return False
    
    def get_keys(self,dict,value):
        dict_inverse={value:key for key,value in dict.items()}
        return dict_inverse[value]

solution 2 a little optimization:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        other={}
        for i in range(len(nums)):
            if nums[i] in other:
                return [i,other[nums[i]]]
            else:
                other[target-nums[i]]=i

further deeper

Screen Shot 2020-02-23 at 9.17.02 AM.png
solution 1: Time limited

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result=[]
        nums=sorted(nums)
     
        for i,num in enumerate(nums[:-2]):   
            if i>0 and nums[i]==nums[i-1]:
                continue
                
            res=-num
            for j in range(i+1,len(nums)-1):
                if j>i+1 and nums[j]==nums[j-1]:
                    continue
                ress=res-nums[j]
                for z in range(j+1,len(nums)):
                    if z>j+1 and nums[z]==nums[z-1]:
                        continue
                    if ress==nums[z]:
                        result.append([num,nums[j],nums[z]])
        return result

 class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = []
        nums = sorted(nums)
        
        for i, num in enumerate(nums[:-2]):
            if nums[i]>0:
                break 
            if nums[i]==nums[i-1] and i>=1:
                continue

            l = i + 1
            h = len(nums) - 1

            while l < h:
                sum3 = num + nums[l] + nums[h]
                if sum3 < 0:
                    l += 1
                elif sum3 > 0:
                    h -= 1
                elif sum3==0:
                    result.append([nums[i], nums[l], nums[h]])
                    l+=1
                    h-=1
                    while nums[l]==nums[l-1] and l<len(nums)-1:
                        l+=1
                    while nums[h]==nums[h+1] and h<len(nums)-2:
                        h-=1

        return result