【leetcode】day1

开始刷题！

001 ：两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

具体问题见网址

001.暴力解法 （双for循环）

001.暴力解法 （双for循环） java版

解法时间复杂度约为 $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中的length为 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; // 如果只有上面的return 会导致部分循环没有返回值，导致报错
    }
}

001.暴力解法 （双for循环） pyhton版

class Solution(object):
    def twoSum(self, nums, target):
        result=[];
        for i in range(0,len(nums)): # 注意 python for循环 if 后面加“：”
            for j in range(i+1,len(nums)): 
                if ((nums[i]+nums[j])==target):
                    result.append(i);
                    result.append(j);
        
        return result

001.hash解法

利用hash表的方式求解，关键在于hash表的查找速度特别块。此外 python的字典与hash表类似

001.hashmap java版

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<>(); // 建立k-v ，一一对应的哈希表
    // 注意 hash表，数组的值作为key值,数组的下标作为value值
    //（为什么？在查找数组的时候我们关注的是数组的值，而不是下标，我们需要以值为“导向” 来查找所需要的数组）.
    // 不用担心数组的值作为key值会重复,因为如果重复的话,覆盖即可
    for(int i = 0; i < nums.length; i++){
    
        int temp = target - nums[i];
        
        if(map.containsKey(temp)){
    
        // 判断 hash表中是否存在target - nums[i] 这个值，如果存在直接返回 
            result [1] = i;
            result [0] = map.get(temp);
            return result;
        }
        // 如果不存在就将 键值对存入，以备查找（这些键值对是已经确定的、任意两个数字之间没有所需要和等于target的数组）
        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];  # 注意 以 key 访问 字典时 要用方括号！！！
            dict1[num]=index;
        
        return None;