【leetcode】day1

Start to brush the questions ！

001 ： Sum of two numbers

Given an array of integers nums And an integer target value target, Please find... In the array and For the target target the Two Integers , And return their array subscripts .
You can assume that each input corresponds to only one answer . however , The same element in the array cannot be repeated in the answer . You can return the answers in any order .

For specific questions, see website

001. Violence solution （ double for loop ）

001. Violence solution （ double for loop ） java edition

The time complexity of the solution is about $O(n^2)$

class Solution {
    
    public int[] twoSum(int[] nums, int target) {
    
        int[] result=new int[2];
        for (int i=0;i<(nums.length-1);i++){
    //java Medium length by  nums.length
            for (int j=i+1;j<nums.length;j++){
    
                if ((nums[i]+nums[j])==target)
                {
    
                    result[0]=i;
                    result[1]=j;
                    return result;   
                } 
            }
        }
        return result; //  If only the above return  It will cause some loops to have no return value , Result in an error 
    }
}

001. Violence solution （ double for loop ） pyhton edition

class Solution(object):
    def twoSum(self, nums, target):
        result=[];
        for i in range(0,len(nums)): #  Be careful  python for loop  if  Back plus “：”
            for j in range(i+1,len(nums)): 
                if ((nums[i]+nums[j])==target):
                    result.append(i);
                    result.append(j);
        
        return result

001.hash solution

utilize hash Solve by table , The key lies in hash The lookup speed of the table is particularly fast . Besides python A dictionary of hash The table is similar

001.hashmap java edition

import java.util.HashMap;
import java.util.Map;
public int[] twoSum(int[] nums, int target) {
    
    int[] result = new int[2];
    if(nums == null || nums.length == 0){
    
        return result ;
    }
    Map<Integer, Integer> map = new HashMap<>(); //  establish k-v , One to one hash table 
    //  Be careful  hash surface , The value of the array is used as key value , The subscript of the array is used as value value 
    //（ Why? ？ When looking for an array, we focus on the value of the array , Instead of Subscripts , We need to take value as “ guide ”  To find the required array ）.
    //  Don't worry about array values as key The value repeats , Because if you repeat , Cover can 
    for(int i = 0; i < nums.length; i++){
    
        int temp = target - nums[i];
        
        if(map.containsKey(temp)){
    
        //  Judge  hash Is there... In the table target - nums[i]  This value , If there is a direct return  
            result [1] = i;
            result [0] = map.get(temp);
            return result;
        }
        //  If it doesn't exist, it will   Key value pairs are stored , In case you want to find （ These key value pairs have been determined 、 There is no required sum between any two numbers target Array of ）
        map.put(nums[i], i);
    }
    return result ;
}

001.dict pyhton

class Solution(object):
    def twoSum(self, nums, target):
        dict1={
    };
        for index,num in enumerate(nums):
            temp=target-num;
            if temp in dict1: 
                return [dict1[temp],index];  #  Be careful   With  key  visit   Dictionary time   Use square brackets ！！！
            dict1[num]=index;
        
        return None;